Patent Description:
Quality of service (quality of service, QoS) is an indicator reflecting a network status, and the network status includes a state such as network delay or network congestion. To ensure QoS of a network, a packet received by a network device may be added to a queue, and a packet cached in the queue is removed from the queue based on a specific policy.

In combination with a token-bucket (Token-Bucket) technology, the packet stored in the queue is scheduled, and a traffic burst can be shaped. Specifically, a rate at which a token is injected into the token bucket may be limited, to limit a rate at which the packet is removed from the queue. If a rate at which the packet is added to the queue reaches or exceeds the rate at which the token is injected into the token bucket, scheduling of the packet in the queue may be suspended. In this way, burst shaping is implemented.

Further, a combination of a plurality of token buckets may further reduce impact of a burst. The patent <CIT> discloses such an example of issuing tokens to packets from two token buckets. Specifically, if the rate at which the packet is added to the queue is low, the packet may be removed from the queue through scheduling of one token bucket. If the rate at which the packet is added to the queue is high, the packet may be removed from the queue through scheduling of a plurality of token buckets. However, if the packet in the queue is scheduled by using a plurality of token buckets, a problem of frequent token bucket switching may occur.

Embodiments of this application provide a packet scheduling method and apparatus, to reduce a frequency of token bucket switching. The present invention is defined as the subject matter of the claims.

The following describes, with reference to the accompanying drawings, the conventional technology and the packet scheduling method provided in embodiments of this application.

<FIG> is a schematic diagram of a structure of a system <NUM> according to an embodiment of this application. The system <NUM> includes a device <NUM>, a device <NUM>, a network device <NUM>, a network device <NUM>, a network device <NUM>, a network device <NUM>, and a network device <NUM>. The network device <NUM> is separately connected to the device <NUM>, the network device <NUM>, and the network device <NUM>, the network device <NUM> is separately connected to the network device <NUM> and the network device <NUM>, and the device <NUM> is separately connected to the network device <NUM> and the network device <NUM>. The network device <NUM> is connected to the device <NUM> through a network interface A1, the network device <NUM> is connected to the network device <NUM> through a network interface A2, and the network device <NUM> is connected to the network device <NUM> through a network interface A3. Through the network devices in the system, the devices can send packets to each other. For example, the device <NUM> may send a packet to the device <NUM> through a path "network device <NUM>→network device <NUM>", or may send a packet to the device <NUM> through a path "network device <NUM>→network device <NUM>→network device <NUM>-network device <NUM>".

To avoid a traffic burst, one or more token buckets may be configured in the network device <NUM> to determine whether a packet in a queue of the network device <NUM> can be removed from the queue. If a quantity of remaining tokens in a token bucket can satisfy that a packet is to be removed from a queue, the packet may be removed from the queue through scheduling, and subsequent processing is performed on the packet based on the token bucket corresponding to the packet removed from the queue.

For example, it is assumed that the network device <NUM> includes a first token bucket and a second token bucket. In a process of scheduling a packet X to be removed from a queue, the network device <NUM> may first determine whether a quantity of remaining tokens in the first token bucket satisfies that the packet X is to be removed from the queue. If the quantity of remaining tokens in the first token bucket satisfies that the packet X is to be removed from the queue, the network device <NUM> may issue a token in the first token bucket to the packet X, and remove the packet X from the queue. If the quantity of remaining tokens in the first token bucket does not satisfy that the packet X is to be removed from the queue, the network device <NUM> may determine whether a quantity of remaining tokens in the second token bucket satisfies that the packet X is to be removed from the queue. If the quantity of remaining tokens in the second token bucket satisfies that the packet X is to be removed from the queue, the network device <NUM> may issue a token in the second token bucket to the packet X, and remove the packet X from the queue.

After the packet X is removed from the queue, the packet X may be processed based on the token issued to the packet X. For example, in an application scenario shown in <FIG>, if the packet X is a packet sent by the device <NUM> to the device <NUM>, the network device <NUM> may determine a forwarding path of the packet based on the token of the packet X. If the token in the first token bucket is issued to the packet X, the network device <NUM> may send the packet X through the path "network device <NUM> →network device <NUM>". If the token corresponding to the second token bucket is issued to the packet X, the network device <NUM> may send the packet X through the path "network device <NUM>→network device <NUM>-network device <NUM>-network device <NUM>".

In this way, if the network device <NUM> receives a large quantity of packets in a short time, the network device <NUM> may forward the packets through two different paths. In this way, impact of the traffic burst on a network system can be reduced. It may be understood that, even if the network device <NUM> does not forward the packets through two different paths, the network device <NUM> may still perform differentiated processing on the packet to which the token in the first token bucket is issued and the packet to which the token in the second token bucket is issued, to achieve an objective of traffic shaping.

However, a conventional method for performing packet scheduling by using a plurality of token buckets may have a problem of frequent token bucket switching, and consequently, a processing method corresponding to a token bucket may be invoked frequently, which affects the network system. Specifically, if different token buckets correspond to different forwarding paths, frequent token bucket switching may cause actual utilization of a path to be lower than utilization achievable by the path.

For example, in the foregoing application scenario, when a rate at which a packet is added to a queue is greater than a rate at which a token is injected into the first token bucket, the network device <NUM> may schedule and remove the packet from the queue by using the second token bucket; or when a rate at which a packet is added to a queue is less than or equal to a rate at which a token is injected into the first token bucket, the network device <NUM> may schedule and remove the packet from the queue by using the first token bucket. In this case, if the rate at which a packet is added to a queue fluctuates around the rate at which a token is injected into the first token bucket, the network device <NUM> repeatedly performs switching between the first token bucket and the second token bucket for a plurality of times when issuing a token in a token bucket to the packet. If the token in the first token bucket and the token in the second token bucket respectively correspond to different paths, utilization of a path by the network device <NUM> may be lower than actually achievable utilization of the path.

It is assumed that a token is injected into the first token bucket of the network device <NUM> at a rate V; a packet is added to a queue of the network device <NUM> at a rate of <NUM> V between a moment t1 and a moment t2; the packet is added to the queue of the network device <NUM> at a rate of <NUM> V between the moment t2 and a moment t3; and the packet is added to the queue of the network device <NUM> at a rate of <NUM> V between the moment t3 and a moment t4. Correspondingly, the network device <NUM> may forward the packet through the path "network device <NUM>→network device <NUM>" between the moment t1 and the moment t2, and a rate of forwarding the packet corresponds to <NUM> V; the network device <NUM> may forward a part of the packet through the path "network device <NUM>→network device <NUM>" and forward a remaining part of the packet through the path "network device <NUM>→network device <NUM>-network device <NUM>→network device <NUM>" between the moment t2 and the moment t3, a rate of forwarding the packet through the path "network device <NUM>→network device <NUM>" corresponds to V, and a rate of forwarding the packet through the path "network device <NUM>→network device <NUM>→network device <NUM>-network device <NUM>" corresponds to <NUM> V; and the network device <NUM> may forward the packet through the path "network device <NUM>→network device <NUM>" between the moment t3 and the moment t4, and a rate of forwarding the packet corresponds to <NUM> V.

It can be learned that, the rate at which the network device <NUM> forwards the packet through the path "network device <NUM>-network device <NUM>" corresponds to <NUM> V between the moment t1 and the moment t2 and before the moment t3 and the moment t4. In a process from the moment t1 to the moment t4, an average rate at which the network device <NUM> forwards the packet through the path "network device <NUM>→network device <NUM>" is lower than a rate corresponding to V. In other words, in the process from the moment t1 to the moment t4, utilization of the path "network device <NUM>→network device <NUM>" by the network device <NUM> does not reach <NUM>%, but the network device <NUM> may forward the packet through another path. Consequently, actual utilization of the path "network device <NUM>→network device <NUM>" by the network device <NUM> is lower than maximum utilization, and utilization of the path "network device <NUM>→network device <NUM>" by the network device <NUM> is low.

It may be understood that, even if different token buckets correspond to a same forwarding path, if different token buckets correspond to different processing manners, a problem of frequent token bucket switching may still exist in the conventional packet scheduling method, which may cause a problem that actual utilization of processing manners corresponding to some token buckets is lower than achievable theoretical utilization.

To resolve the foregoing problem of frequent token bucket switching, embodiments of this application provide a packet scheduling method and apparatus, to reduce a frequency of token bucket switching, and further improve utilization of a processing manner corresponding to a token bucket.

The packet scheduling method provided in this embodiment of this application may be applied to the system shown in <FIG>. Specifically, the method may be performed by any one or more of the network device <NUM>, the network device <NUM>, the network device <NUM>, the network device <NUM>, and the network device <NUM> in the embodiment shown in <FIG>. The network device may be a device having a forwarding function, for example, a forwarding device such as a router (router) or a switch (switch), or may be a device having a forwarding function such as a server or a terminal device. Specifically, it is assumed that the packet scheduling method provided in this embodiment of this application is performed by the network device <NUM>. For example, the method may be for scheduling a packet received by the network device <NUM> through a network port A1. Optionally, the device <NUM> and the device <NUM> may be terminal devices, servers, or other devices.

In some possible implementations, the packet scheduling method provided in this embodiment of this application may also be performed by an access device. For example, the method may be performed by an access device having a BRAS function, and is for scheduling a packet that is received by the access device and is from a terminal device.

<FIG> is a schematic flowchart of a packet scheduling method according to an embodiment of this application.

S201: When a quantity of remaining tokens in a first token bucket of a first device does not satisfy that a first packet is to be removed from a queue, the first device determines whether a length of a packet cached in the queue is less than a first threshold.

The first device may be a network device or an access device in a network system. For example, in the embodiment shown in <FIG>, the first device may be any one of the network device <NUM>, the network device <NUM>, the network device <NUM>, the network device <NUM>, and the network device <NUM>. In this embodiment of this application, the first device has at least two token buckets: a first token bucket and a second token bucket, and further has a queue for caching a packet. The following describes the token bucket and queue.

The first token bucket is a token bucket that the first device has, and may be configured to store a token. Optionally, the token stored in the first token bucket may be referred to as a first token. The first device may inject the first token into the first token bucket at a first preset rate. Optionally, the first token bucket may have a first threshold, indicating a maximum quantity of tokens that can be accommodated by the first token bucket. After a quantity of remaining tokens in the first token bucket reaches the first threshold, the quantity of remaining tokens in the first token bucket does not continue to increase.

Similar to the first token bucket, the second token bucket is also a token bucket that the first device has, and is configured to store a token. The token stored in the second token bucket may be referred to as a second token, a maximum quantity of tokens that can be accommodated by the second token bucket may be referred to as a second threshold, and a rate at which the first device injects the second token into the second token bucket may be referred to as a second preset rate. It may be understood that, it is assumed that different token buckets may correspond to different forwarding priorities, and a forwarding priority of the second token bucket may be lower than a forwarding priority of the first token bucket. In a process of scheduling and removing a packet from the queue, the first device may preferentially schedule and remove the packet from the queue by using the first token bucket.

Optionally, in some possible implementations, the first token bucket may be referred to as a C token bucket, and the second token bucket may be referred to as a P token bucket.

It should be noted that technical features such as the "token bucket" and the "token" in this embodiment of this application may be virtual concepts, and do not represent a bucket or a token of an entity. For example, in some possible implementations, a variable of a floating point number type or an integer type may indicate the quantity of remaining tokens in the first token bucket or a quantity of remaining tokens in the second token bucket. Optionally, the first threshold and the second threshold may be the same or may be different; and the first preset rate and the second preset rate may be the same or may be different.

In the first device, the queue for caching a packet may also be referred to as a cache queue. After receiving, through a network interface, a packet sent by another device, the first device may first add the packet to the cache queue. A packet stored in the cache queue may be removed from the queue by using the first token bucket or the second token bucket. Optionally, the cache queue may have a queue upper limit. After a quantity of packets cached in the cache queue reaches the queue upper limit, the first device no longer adds a newly received packet to the cache queue. For example, the first device may discard a packet received after the quantity of packets cached in the cache queue reaches the queue upper limit. The queue upper limit may be determined by storage space allocated by the first device to the cache queue, or may be divided by a skilled person based on an actual application situation. The quantity of packets may indicate a quantity of packets or a total quantity of bytes of packets.

Optionally, after receiving a new packet, the first device may add the packet to a tail of the queue. However, in a process of scheduling and removing a packet from the queue, the first device may preferentially schedule a packet located at a head of the queue. In other words, the first device may schedule the packet based on a time at which the packet is added to the queue. An earlier time at which the packet is added to the queue indicates an earlier time at which the packet is removed from the queue. Correspondingly, the "first packet" described below may be the <NUM>st packet located at the head of the queue in the queue.

After the first device determines that a determining trigger condition is satisfied, the first device may determine whether the quantity of remaining tokens in the first token bucket satisfies that the first packet is to be removed from the queue. The determining trigger condition indicates possibility that the first packet is to be removed from the queue. Specifically, the determining trigger condition may include any one or more of the following: the quantity of remaining tokens in the first token bucket increases, the quantity of remaining tokens in the second token bucket increases, the network device adds a new packet to the queue, and the network device removes a packet from the queue. Optionally, that the quantity of remaining tokens in the first token bucket satisfies that the first packet is to be removed from the queue may include that the quantity of remaining tokens in the first token bucket is greater than or equal to a quantity of bytes of the first packet.

In this embodiment of this application, the first device may perform a corresponding operation based on a determining result. The following separately describes two possible implementations corresponding to two determining results.

In a first possible implementation, the first device determines that the quantity of remaining tokens in the first token bucket cannot satisfy the condition that the first packet is to be removed from the queue. In this case, the first device may determine whether the length of the packet cached in the queue is less than the first threshold, and schedule the first packet based on a determining result. That the quantity of remaining tokens in the first token bucket cannot satisfy the condition that the first packet is to be removed from the queue may include that the quantity of remaining tokens in the first token bucket is less than the quantity of bytes of the first packet.

In this embodiment of this application, the first threshold may be a threshold for enabling the second token bucket. Before scheduling and removing the packet from the queue by using the second token bucket, the first device may first determine that the length of the packet cached in the queue is greater than the first threshold. Optionally, the length of the packet cached in the queue may include a total quantity of bytes of all packets cached in the queue, and a unit of the first threshold may be byte (Byte). In some possible implementations, the length of the packet cached in the queue may also include a total quantity of packets cached in the queue.

In a second possible implementation, the first device determines that the quantity of remaining tokens in the first token bucket can satisfy the condition that the first packet is to be removed from the queue. In this case, the first device may issue a token in the first token bucket to the first packet, and remove the first token bucket from the queue. Issuing the token in the first token bucket to the first packet is to process the first packet in a processing manner corresponding to the first token bucket in a subsequent processing process. Optionally, the issuing the token in the first token bucket to the first packet may include adding a marker corresponding to the first token bucket to the first packet, or may include recording the first packet as a packet that is scheduled, by using the first token bucket, to be the removed from the queue. For descriptions of a processing method corresponding to the token in the first token bucket, refer to the following descriptions.

Optionally, if the token in the first token bucket is issued to the first packet, the first device may adjust the quantity of remaining tokens in the first token bucket based on the first packet after the first packet is removed from the queue. For example, the first device may remove some or all tokens from the first token bucket, and a quantity of removed tokens may be equal to a quantity of bytes of a target packet. Assuming that a quantity of tokens represents a quantity of bytes that can be scheduled, after a packet whose quantity of bytes is i is removed from the queue through scheduling, the first device may remove i tokens from the first token bucket.

S202: In response to that the length of the packet cached in the queue is not less than the first threshold, the first device issues a token in the second token bucket to the first packet, and removes the first packet from the queue.

If the first device determines that the length of the packet cached in the queue is not less than the first threshold, the first device may issue the token in the second token bucket to the first packet, and remove the first packet from the queue. The first threshold is a threshold for the first device to enable the second token bucket to perform packet scheduling. If the length of the packet cached in the queue is greater than or equal to the first threshold, the first device may enable the second token bucket to schedule the packet cached in the queue to be removed from the queue. Optionally, the first threshold may indicate a length of a packet that may cause network congestion, for example, may be <NUM>% of the foregoing queue threshold. Alternatively, the first threshold may be determined based on a burst limit that can be tolerated in the processing manner corresponding to the first token bucket. In other words, in the processing manner corresponding to the first token bucket, that a packet less than or equal to the first threshold is not scheduled can be tolerated.

Optionally, the length of the packet cached in the queue may be a quantity of packets cached in the queue, or may be a total quantity of bytes of the packets cached in the queue.

In this embodiment of this application, the first device issues the token in the second token bucket to the first packet, to process the first packet in a processing manner corresponding to the second token bucket in a subsequent processing process. Optionally, the issuing the token in the second token bucket to the first packet may include adding a marker corresponding to the second token bucket to the first packet, or may include recording the first packet as a packet that is scheduled, by using the second token bucket, to be removed from the queue. For descriptions of a processing method corresponding to the token in the second token bucket, refer to the following descriptions.

Similar to the token in the first token bucket, if the token in the second token bucket is issued to the first packet, the first device may adjust the quantity of remaining tokens in the second token bucket based on the first packet after the first packet is removed from the queue.

In some possible cases, the quantity of remaining tokens in the second token bucket may not satisfy that the first packet is to be removed from the queue. For example, the quantity of remaining second tokens in the second token bucket may be less than the quantity of bytes of the first packet. In this case, the first device may not remove the first packet from the queue. In other words, when neither the quantity of remaining tokens in the first token bucket nor the quantity of remaining tokens in the second token bucket satisfies that the first packet is to be removed from the queue, the first device may keep the first packet in the queue. Because a quantity of remaining tokens in a token bucket may gradually increase with time, the first device may wait until the quantity of remaining tokens in the first token bucket (or the second token bucket) is accumulated to satisfy the condition that the first packet is to be removed from the queue, and then remove the first packet from the queue.

In this embodiment of this application, the first threshold is the threshold for the first device to enable the second token bucket. In this case, if the length of the packet cached in the queue of the first device is less than the first threshold, it indicates that the queue does not reach the threshold for the first device to enable the second token bucket, and the first device may not schedule and remove the packet from the queue by using the second token bucket. It may be understood that, even if the quantity of remaining tokens in the first token bucket does not satisfy the condition that the first packet is to be removed from the queue, if the length of the packet cached in the queue is less than the first threshold, the first device may not schedule and remove the first packet from the queue, and keep the first packet in the cache queue. In other words, in addition to a status of the first token bucket, the first device may further determine, based on the length of the packet cached in the queue, whether to use the second token bucket to schedule and remove the first packet from the queue. In this way, by determining whether the length of the packet cached in the queue is less than the first threshold, when the quantity of remaining tokens in the first token bucket is insufficient, the first device does not directly schedule and remove the packet from the queue by using the second token bucket, so that frequent switching between the first token bucket and the second token bucket is avoided, and utilization of the processing manner corresponding to the first token bucket is improved.

For example, it is assumed that a rate at which a packet is added to a queue fluctuates up and down based on the first preset rate. When the rate at which a packet is added to a queue is higher than the first preset rate, the quantity of remaining tokens in the first token bucket may not satisfy that the packet is to be removed from the queue. In this case, the first device may keep, in the queue, the packet that is added to the queue but cannot be scheduled. When the rate at which a packet is added to a queue is lower than the first preset rate, the packet added to the queue cannot fully consume the token injected into the first token bucket. In this case, the remaining tokens in the first token bucket may be configured to schedule the packet cached in the queue to be removed from the queue, thereby reducing the quantity of packets cached in the queue. In this way, it is equivalent to using the token injected into the first token bucket when the rate at which a packet is added to a queue is low, and scheduling is performed on a packet that cannot be scheduled in the queue when the rate at which a packet is added to a queue is high. In this way, the queue is used as a buffer, so that frequent switching between the first token bucket and the second token bucket is avoided, and traffic shaping of a packet flow is implemented.

The foregoing describes a method in which the first device schedules and removes the first packet from the queue. The following describes a method for processing, by the first device, the first packet based on a token issued to the first packet after the first packet is removed from the queue.

In this embodiment of this application, the first device may determine a forwarding path of the first packet based on the token issued to the first packet, or may determine a forwarding priority of the first packet based on the token issued to the first packet. The following separately describes the two implementations.

In a first possible implementation, the first device determines the forwarding path of the first packet based on the token issued to the first packet. In other words, the token in the first token bucket corresponds to a forwarding path, and the token in the second token bucket may correspond to another forwarding path. In this embodiment of this application, the forwarding path corresponding to the token in the first token bucket may be referred to as a second path, and the forwarding path corresponding to the token in the second token bucket may be referred to as a first path.

It can be learned from the foregoing descriptions that, when the rate at which a packet is added to a queue is low, the first device may preferentially schedule and remove the packet from the queue by using the first token bucket. In other words, the network device may preferentially select the second path to forward the packet. In this case, the second path corresponding to the first token bucket may be a path with high link quality. That is, link quality of the second path may be higher than link quality of the first path.

Correspondingly, after the first packet is removed from the queue, the first device may determine the forwarding path of the first packet from the first path and the second path based on the token issued to the first packet, thereby determining an outbound interface for sending the first packet, and sending the first packet from the corresponding outbound interface. If the token in the first token bucket is issued to the first packet, the first device may forward the first packet through an outbound interface corresponding to the second path. If the token in the second token bucket is issued to the first packet, the first device may forward the first packet through an outbound interface corresponding to the first path.

The following uses <FIG> as an example for description. It is assumed that the first device is the network device <NUM> in <FIG>, and the first packet is a packet X sent by the device <NUM> to the device <NUM>. It can be learned from the structural diagram of the system shown in <FIG> that the network device <NUM> may receive the packet X through the network interface A1, and forward the packet through the network interface A2 or the network interface A3. Correspondingly, the method provided in this embodiment of this application may be applied to an inbound interface of the network device <NUM>, namely, the network interface A1, configured to forward the packet X based on a status of a token bucket and a queue after the network device <NUM> receives the packet X.

Optionally, because a path "network device <NUM>→network device <NUM>→network device <NUM>-network device <NUM>" passes through a large quantity of network devices, link quality of the path "network device <NUM> -network device <NUM>-network device <NUM>-network device <NUM>" may be low. For example, a delay value of the path may be high.

Therefore, the path "network device <NUM>→network device <NUM>-network device <NUM>-network device <NUM>" may be determined as the first path, and a path "network device <NUM>→network device <NUM>" may be determined as the second path.

After the packet X is removed from the queue, if the token in the first token bucket is issued to the packet X, the network device <NUM> may schedule the packet X to be removed from the queue through the network interface A2, so that the packet X is forwarded through the path "network device <NUM>→network device <NUM>"; or if the token in the second token bucket is issued to the packet X, the network device <NUM> may schedule the packet X to be removed from the queue through the network interface A3, so that the packet X is forwarded through the path "network device <NUM>→network device <NUM>→network device <NUM>→network device <NUM>". In this way, when a rate at which a packet is added to a queue is low, the network device <NUM> may forward the packet through the path "network device <NUM>→network device <NUM>" with high link quality. As the rate at which a packet is added to a queue increases, the network device <NUM> may share pressure of the path "network device <NUM>→network device <NUM>" through the path "network device <NUM>-network device <NUM>-network device <NUM>-network device <NUM>". In addition, the queue and the first threshold are used for buffering, so that frequent switching between the first token bucket and the second token bucket can be avoided, and traffic shaping of the packet flow is implemented.

In some possible implementations, a network type of an access network in which the first path is located may be different from a network type of an access network in which the second path is located. In other words, the first device may select, based on a situation in which a packet is added to a queue, different access networks to forward the packet. In this case, the access network in which the second path is located may have better performance than the access network in which the first path is located. The first device preferentially forwards the first packet through the second path, so that a QoS parameter of the first packet can be improved, or packet forwarding costs can be reduced.

For example, for a hybrid access aggregation point (Hybrid Access Aggregation Point, HAAP) in a hybrid access (Hybrid Access, HA) scenario, a user may be supported to be bound to two types of access networks: a digital subscriber line (Digital Subscriber Line, DSL) and/or long term evolution (Long Term Evolution, LTE). For some user services, the packet may be preferentially transmitted through a path corresponding to the DSL. When a bandwidth of the DSL is insufficient, the packet is transmitted through a path corresponding to the LTE. In this case, the first path may be the path corresponding to the LTE, and the second path may be the path corresponding to the DSL.

In some other possible implementations, a network type of a network in which the first path is located may be the same as a network type of a network in which the second path is located, but costs of forwarding the packet by using the network in which the first path is located may be different from costs of forwarding the packet by using the network in which the second path is located. For example, a bandwidth of the first path may be greater than a bandwidth of the second path. In this way, in a process of forwarding the packet, the first device may preferentially use the second path with a small bandwidth to forward the packet, and then use a first queue to forward the packet when the rate at which a packet is added to a queue is high and the bandwidth of the second path is greatly occupied. In this way, utilization of the second path can be improved, thereby reducing packet transmission costs.

In a second possible implementation, the first device determines the forwarding priority of the first packet based on the token issued to the first packet. The forwarding priority indicates the network device that forwards the first packet to forward the first packet. The first token bucket and the second token bucket respectively correspond to different forwarding priorities. As tokens issued to the first packet are different, forwarding priorities set by the first device for the first packet are also different. In this embodiment of this application, a forwarding priority corresponding to the token in the first token bucket is referred to as a second priority, and a forwarding priority corresponding to the token in the second token bucket is referred to as a first priority. Optionally, a forwarding priority of the first priority is lower than a forwarding priority of the second priority. That is, in a process of forwarding a packet, the device may preferentially forward a packet with a first priority.

After determining the forwarding priority of the first packet, the first device may forward the first packet based on the forwarding priority of the first packet. Optionally, the first device may add, to the first packet, a marker indicating the forwarding priority, and then send the marked first packet to a next-hop device. In this way, the next-hop device may determine the forwarding priority of the first packet based on the marker in the first packet, to select a forwarding manner corresponding to the forwarding priority to forward the first packet.

An example is used for description. It is assumed that the method provided in this embodiment of this application is applied to the network device <NUM> in <FIG>, and the first packet is a packet Y sent by the device <NUM> to the device <NUM>. After scheduling the packet Y to be removed from the queue, the network device <NUM> may determine a forwarding priority of the packet Y based on a token issued to the packet Y, and add a corresponding marker to the packet Y. Assuming that the token in the first token bucket is issued to the packet Y, the network device <NUM> may determine that the forwarding priority of the packet Y is the second priority, and add a marker corresponding to the second priority to the packet Y. For example, the network device may mark the packet Y in a green (Green) state. Assuming that the token in the second token bucket is issued to the packet Y, the network device <NUM> may determine that the forwarding priority of the packet Y is the first priority, and add a marker corresponding to the first priority to the packet Y. For example, the network device may mark the packet Y in a yellow (Yellow) state.

After adding the marker to the packet Y, the network device <NUM> may send the packet Y to the network device <NUM>. A single rate three color marker (Single Rate Three Color Marker, SRTCM) algorithm or a two rate three color marker (Two Rate Three Color Marker, TRTCM) algorithm may be deployed on the network device <NUM>. By using the SRTCM algorithm or the TRTCM algorithm, the network device <NUM> may determine a scheduling manner of the packet Y based on the marker in the packet Y, to forward the packet Y based on the forwarding priority.

In the foregoing descriptions, the first device may determine the forwarding path of the first packet based on the token issued to the first packet, or may determine the forwarding priority of the first packet based on the token issued to the first packet. In some possible implementations, the first device may determine the forwarding path and the forwarding priority of the first packet based on the token issued to the first packet.

For ease of understanding, the following uses an example in which the network device <NUM> is configured to receive a packet flow from the device <NUM>, and a target device of each packet in the packet flow is the device <NUM> for description. The token in the first token bucket corresponds to the first path, and the token in the second token bucket corresponds to the second path.

<FIG> is a method flowchart of a packet scheduling method according to an embodiment of this application.

S301: A network device <NUM> receives a packet M.

As shown in <FIG>, the network device <NUM> may receive, through a network interface A1, the packet M sent by a device <NUM>. After the packet M receives the packet M, the network device <NUM> may serve as a first device to perform the packet scheduling method provided in this embodiment of this application.

S302: The network device <NUM> determines whether a length of a packet cached in a queue is not less than a threshold.

After receiving the packet M, the network device <NUM> may determine whether the length of the packet cached in the queue is not less than the threshold. The queue is a queue for storing a to-be-scheduled packet, and the threshold may be a maximum value of a length of a packet that can be accommodated by the queue, or a difference between a maximum value of a length of a packet that can be accommodated by the queue and a length of the packet M. Optionally, the threshold may be represented by a quantity of packets or a total quantity of bytes of packets.

If the length of the packet cached in the queue is greater than or equal to the threshold, it indicates that no new packet can be added to the queue, and the network device <NUM> may perform step S303. If the length of the packet cached in the queue is less than the threshold, the network device <NUM> may perform step S304.

Optionally, if the threshold is the difference between the maximum value of the length of the packet that can be accommodated by the queue and the length of the packet M, the network device <NUM> may also perform step S304 when the length of the packet cached in the queue is equal to the threshold.

S303: The network device <NUM> discards the packet M.

If the length of the packet cached in the queue is not less than the threshold, it indicates that the packet cached in the queue is equal to or close to a maximum capacity that can be accommodated by the queue, and the queue cannot accommodate another packet. As a result, the packet M cannot be added to the queue. In this case, the network device <NUM> may discard the packet M.

Optionally, in some possible implementations, the network device <NUM> may alternatively not discard the packet M when the length of the packet cached in the queue is greater than or equal to the threshold. For example, the network device <NUM> may store the packet M in another storage location different from the queue, to schedule the packet M when a condition is satisfied.

S304: The network device <NUM> adds the packet M to the queue.

If the length of the packet cached in the queue is less than the threshold, it indicates that the packet cached in the queue does not reach the maximum capacity that can be accommodated by the queue, and the queue can continue to accommodate another packet. In this case, the network device <NUM> may add the packet M to the queue, and continue to perform step S305. Optionally, the network device <NUM> may add the packet M to a tail of the queue.

S305: The network device <NUM> determines whether remaining tokens in a first token bucket satisfy that a target packet is to be removed from the queue.

After the packet M is added to the queue, the network device <NUM> may determine whether the remaining tokens in the first token bucket satisfy that the target packet is to be removed from the queue. The target packet is a packet that is cached in the queue and that is located at a head of the queue. That is, the target packet is the <NUM>st packet that needs to be scheduled in the to-be-scheduled packet. Optionally, before the target packet is removed from the queue, another packet in the queue is kept in the queue and is not removed from the queue. It may be understood that, as the target packet is removed from the queue, the network device <NUM> may determine, as a new target packet, a packet that is located at the head of the queue after the target packet is removed from the queue, that is, the target packet is always the <NUM>st to-be-scheduled packet in the queue.

Optionally, the network device <NUM> may determine, through comparison, whether a quantity of remaining tokens in the first token bucket is greater than or equal to a quantity of bytes of the target packet. If the quantity of remaining tokens in the first token bucket is greater than or equal to the quantity of bytes of the target packet, the network device may determine that the remaining tokens in the first token bucket satisfy that the target packet is to be removed from the queue, and perform step S306. If the quantity of remaining tokens in the first token bucket is greater than or equal to the quantity of bytes of the target packet, the network device may determine that the remaining tokens in the first token bucket do not satisfy that the target packet is to be removed from the queue, and perform step S307.

For a specific process of determining, by the network device <NUM>, whether the remaining tokens in the first token bucket satisfy that the target packet is to be removed from the queue, refer to the descriptions in the embodiment corresponding to <FIG>.

S306: The network device <NUM> forwards the target packet through a second path.

If it is determined that the remaining tokens in the first token bucket satisfy that the target packet is to be removed from the queue, the network device <NUM> may issue a token in the first token bucket to the target packet, and schedule and remove the target packet from the queue. Then, the network device <NUM> may forward the target packet through the second path corresponding to the token in the first token bucket. In the application scenario shown in <FIG>, the second path may be a path "network device <NUM>→network device <NUM>". For descriptions of determining a forwarding path by the network device <NUM>, refer to the foregoing descriptions.

After the target packet is removed from the queue through scheduling, the network device <NUM> may adjust the quantity of remaining tokens in the first token bucket. For example, some or all tokens may be removed from the first token bucket, and a quantity of removed tokens may be equal to the quantity of bytes of the target packet.

After the target packet is removed from the queue through scheduling, the network device <NUM> may determine the packet located at the head of the queue as the new target packet, and return to perform step S305.

S307: The network device <NUM> determines whether the length of the packet cached in the queue is not less than a first threshold.

If it is determined that the remaining tokens in the first token bucket do not satisfy that the target packet is to be removed from the queue, the network device <NUM> may further determine whether the length of the packet cached in the queue is less than the first threshold. If the length of the packet cached in the queue is not less than the first threshold, the network device <NUM> may perform step S308; or if the length of the packet cached in the queue is less than the first threshold, the network device <NUM> may perform step S310.

S308: The network device <NUM> determines whether remaining tokens in a second token bucket satisfy that the target packet is to be removed from the queue.

It can be learned from the foregoing descriptions that the "first threshold" in this embodiment of this application is a threshold for enabling the second token bucket to perform packet scheduling. If the length of the packet cached in the queue is greater than or equal to the first threshold, it indicates that the network device <NUM> may enable the second token bucket to schedule the packet. In a process of scheduling the packet by using the second token bucket, the network device <NUM> may first determine whether the remaining tokens in the second token bucket satisfy that the target packet is to be removed from the queue. For a specific process of determining, by the network device <NUM>, whether the remaining tokens in the second token bucket satisfy that the target packet is to be removed from the queue, refer to the descriptions in the foregoing corresponding embodiment.

If the remaining tokens in the second token bucket satisfy that the target packet is to be removed from the queue, it indicates that the second token bucket allows the network device <NUM> to remove the target packet from the queue based on the second token bucket, and the network device <NUM> may perform step S309; or if the remaining tokens in the second token bucket do not satisfy that the target packet is to be removed from the queue, it indicates that the network device <NUM> cannot schedule and remove the target packet from the queue by using the second token bucket, and the network device <NUM> may perform step S310.

S309: The network device <NUM> forwards the target packet through a first path.

If it is determined that the remaining tokens in the second token bucket satisfy that the target packet is to be removed from the queue, the network device <NUM> may issue a token in the second token bucket to the target packet, and schedule and remove the target packet from the queue. Then, the network device <NUM> may forward the target packet through the first path corresponding to the token in the second token bucket. In the application scenario shown in <FIG>, the first path may be a path "network device <NUM>→network device <NUM>→network device <NUM>→network device <NUM>". For descriptions of determining a forwarding path by the network device <NUM>, refer to the foregoing descriptions.

Similar to step S306, the network device <NUM> may adjust a quantity of remaining tokens in the second token bucket after the target packet is removed from the queue through scheduling. For example, some or all tokens may be removed from the second token bucket, and a quantity of removed tokens may be equal to the quantity of bytes of the target packet. In addition, after the target packet is removed from the queue through scheduling, the network device <NUM> may determine the packet located at the head of the queue as the new target packet, and return to perform step S305.

S310: The network device <NUM> keeps the target packet in the queue.

If the length of the packet cached in the queue is less than the first threshold, or the remaining tokens in the second token bucket do not satisfy that the target packet is to be removed from the queue, the network device <NUM> may keep the target packet in the queue, and do not schedule and remove the target packet from the queue. Specifically, if the length of the packet cached in the queue is less than the first threshold, the network device <NUM> does not enable the second token bucket to schedule the packet. In this case, because the remaining tokens in the first token bucket do not satisfy that the target packet is to be removed from the queue, the network device <NUM> may keep the target packet in the queue, and does not schedule and remove the target packet from the queue. If the remaining tokens in the second token bucket do not satisfy that the target packet is to be removed from the queue, even if the length of the packet cached in the queue is greater than or equal to the first threshold, the second token bucket is insufficient to remove the target packet from the queue. In this case, the network device <NUM> may keep the target packet in the queue, and does not schedule and remove the target packet from the queue.

It should be noted that, when the length of the packet cached in the queue is less than the first threshold, regardless of the quantity of remaining tokens in the second token bucket, the network device <NUM> may not enable the second token bucket to schedule the packet, and keeps the target packet not removed from the queue.

It may be understood that, in some possible cases, as the new packet is added to the queue, the length of the packet cached in the queue is increased from being less than the first threshold to being the first threshold or being greater than the first threshold. In this case, after determining that the length of the packet cached in the queue is increased to the first threshold or greater than the first threshold, the network device <NUM> may enable the second token bucket to schedule the target packet.

S311: The network device <NUM> adjusts the quantity of remaining tokens in the first token bucket, and/or adjusts the quantity of remaining tokens in the second token bucket.

In a packet scheduling process, the network device <NUM> may adjust the quantity of remaining tokens in the first token bucket based on a first preset rate, and/or the network device <NUM> may adjust the quantity of remaining tokens in the second token bucket based on a second preset rate. Optionally, the network device may periodically inject tokens into the first token bucket and/or the second token bucket.

After the token is injected into the first token bucket or the second token bucket, the network device <NUM> may return to perform step S305, to determine whether the token bucket satisfies the condition that the packet is to be removed from the queue.

It should be noted that, for ease of description, in the flowchart shown in <FIG>, step S311 is performed after step S310. Actually, there is no sequence relationship between injection of the token in the token bucket and keeping of the target packet in the queue, that is, step S311 may be performed at any moment. In an actual application scenario, adjustment of a level quantity of remaining tokens in a token bucket is irrelevant to whether a packet is to be removed from a queue.

Refer to <FIG>. An embodiment of this application further provides a packet scheduling apparatus <NUM>. The packet scheduling apparatus <NUM> may implement functions of the first device in the embodiment shown in <FIG> or <FIG>. The packet scheduling apparatus <NUM> includes a determining unit <NUM> and a scheduling unit <NUM>. The determining unit <NUM> is configured to implement S201 in the embodiment shown in <FIG>, and the scheduling unit <NUM> is configured to implement S202 in the embodiment shown in <FIG>.

Specifically, the determining unit <NUM> is configured to: when a quantity of remaining tokens in a first token bucket does not satisfy that a first packet is to be removed from a queue, determine whether a length of a packet cached in the queue is less than a first threshold.

The scheduling unit <NUM> is configured to: in response to that the length of the packet cached in the queue is not less than the first threshold, issue a token in a second token bucket to the first packet, and remove the first packet from the queue.

For a specific execution process, refer to detailed descriptions of corresponding steps in the embodiment shown in <FIG> or <FIG>.

It should be noted that, in this embodiment of this application, division into the units is an example, and is merely a logical function division. During actual implementation, another division manner may be used. Functional units in embodiments of this application may be integrated into one processing unit, or each of the units may exist alone physically, or two or more units are integrated into one unit. For example, in the foregoing embodiment, the scheduling unit and the determining unit may be a same unit or different units.

<FIG> is a schematic diagram of a structure of a device <NUM> according to an embodiment of this application. The foregoing packet scheduling apparatus <NUM> may be implemented by using the device shown in <FIG>. Refer to <FIG>. The device <NUM> includes at least one processor <NUM>, a communication bus <NUM>, and at least one network interface <NUM>. Optionally, the device <NUM> may further include a memory <NUM>.

The processor <NUM> may be a general-purpose central processing unit (Central Processing Unit, CPU), an application-specific integrated circuit (Application-specific Integrated Circuit, ASIC), or one or more integrated circuits (Integrated Circuit, IC) configured to control program execution of the solution of this application. The processor may be configured to process a packet and a token bucket, to implement the packet scheduling method provided in embodiments of this application.

For example, when the first device in <FIG> is implemented by using the device shown in <FIG>, the processor may be configured to: when a quantity of remaining tokens in a first token bucket does not satisfy that a first packet is to be removed from a queue, determine whether a length of a packet cached in the queue is less than a first threshold; and in response to that the length of the packet cached in the queue is not less than the first threshold, issue a token in a second token bucket to the first packet, and remove the first packet from the queue.

The communication bus <NUM> is configured to transmit information among the processor <NUM>, the network interface <NUM>, and the memory <NUM>.

The memory <NUM> may be a read-only memory (Read-only Memory, ROM) or another type of static storage device that can store static information and instructions, or the memory <NUM> may be a random access memory (Random Access Memory, RAM) or another type of dynamic storage device that can store information and instructions, or may be a compact disc read-only memory (Compact Disc Read-only Memory, CD-ROM) or another compact disc storage, optical disc storage (including a compressed optical disc, a laser disc, an optical disc, a digital versatile optical disc, a Blu-ray disc, or the like), a magnetic disk storage medium or another magnetic storage device, or any other medium that can be configured to carry or store expected program code in a form of instructions or a data structure and can be accessed by a computer. This is not limited thereto. The memory <NUM> may exist independently, and is connected to the processor <NUM> through the communication bus <NUM>. The memory <NUM> may alternatively be integrated with the processor <NUM>.

Optionally, the memory <NUM> is configured to store program code or instructions for executing the technical solutions provided in embodiments of this application, and the processor <NUM> controls the execution. The processor <NUM> is configured to execute the program code or the instructions stored in the memory <NUM>. The program code may include one or more software modules. Optionally, the processor <NUM> may also store the program code or the instructions for executing the technical solutions provided in embodiments of this application. In this case, the processor <NUM> does not need to read the program code or the instructions from the memory <NUM>.

The network interface <NUM> may be an apparatus such as a transceiver, and is configured to communicate with another device or a communication network. The communication network may be Ethernet, a radio access network (RAN), a wireless local area network (Wireless Local Area Network, WLAN), or the like. In this embodiment of this application, the network interface <NUM> may be configured to receive a packet sent by another node in a segment routing network, or may send a packet to another node in a segment routing network. The network interface <NUM> may be an Ethernet interface (Ethernet) interface, a fast Ethernet (Fast Ethernet, FE) interface, a gigabit Ethernet (Gigabit Ethernet, GE) interface, or the like.

In specific implementation, in an embodiment, the device <NUM> may include a plurality of processors, for example, the processor <NUM> and a processor <NUM> shown in <FIG>. Each of the processors may be a single-core (single-CPU) processor, or may be a multi-core (multi-CPU) processor. The processor herein may be one or more devices, circuits, and/or processing cores configured to process data (for example, computer program instructions).

<FIG> is a schematic diagram of a structure of a device <NUM> according to an embodiment of this application. The first device in <FIG> or <FIG> may be implemented by using the device shown in <FIG>. Refer to the schematic diagram of the structure of the device shown in <FIG>. The device <NUM> includes a main control board and one or more interface boards. The main control board is communicatively connected to the interface board. The main control board is also referred to as a main processing unit (Main Processing Unit, MPU) or a route processor card (Route Processor Card). The main control board includes a CPU and a memory. The main control board is responsible for controlling and managing each component in the device <NUM>, including route calculation, device management and function maintenance. The interface board is also referred to as a line processing unit (Line Processing Unit, LPU) or a line card (Line Card), and is configured to receive and send packets. In some embodiments, the main control board communicates with the interface board through a bus, or the interface boards communicate with each other through a bus. In some embodiments, the interface boards communicate with each other through a switching board. In this case, the device <NUM> also includes the switching board. The switching board is communicatively connected to the main control board and the interface board, and is configured to forward data between the interface boards. The switching board may also be referred to as a switch fabric unit (Switch Fabric Unit, SFU). The interface board includes a CPU, a memory, a forwarding engine, and an interface card (Interface Card, IC). The interface card may include one or more network interfaces. The network interface may be an Ethernet interface, an FE interface, a GE interface, or the like. The CPU is communicatively connected to the memory, the forwarding engine, and the interface card. The memory is configured to store a forwarding table. The forwarding engine is configured to forward a received packet based on the forwarding table stored in the memory. If a destination address of the received packet is an IP address of the device <NUM>, the forwarding engine sends the packet to the CPU of the main control board or the CPU of the interface board for processing; or if a destination address of the received packet is not an IP address of the device <NUM>, the forwarding engine searches the forwarding table based on the destination address, and if a next hop and an outbound interface that correspond to the destination address are found from the forwarding table, the forwarding engine forwards the packet to the outbound interface corresponding to the destination address. The forwarding engine may be a network processor (Network Processor, NP). The interface card, also referred to as a subcard, may be installed on the interface board. The interface card is responsible for converting an optical/electrical signal into a data frame, checking validity of the data frame, and forwarding the data frame to the forwarding engine for processing or the CPU of the interface board. In some embodiments, the CPU may also perform functions of the forwarding engine, such as implementing software forwarding based on a general-purpose CPU, so that no forwarding engine is required in the interface board. In some embodiments, the forwarding engine may be implemented by using an ASIC or a field programmable gate array (Field Programmable Gate Array, FPGA). In some embodiments, the memory that stores the forwarding table may alternatively be integrated into the forwarding engine, and is used as a part of the forwarding engine.

An embodiment of this application further provides a chip system, including a processor, where the processor is coupled to a memory, the memory is configured to store a program or instructions, and when the program or the instructions are executed by the processor, the chip system is enabled to implement the packet scheduling method performed by the first device in the embodiment shown in <FIG>.

Optionally, there may be one or more processors in the chip system. The processor may be implemented by using hardware, or may be implemented by using software. When the processor is implemented by using the hardware, the processor may be a logic circuit, an integrated circuit, or the like. When the processor is implemented by using the software, the processor may be a general-purpose processor, and is implemented by reading software code stored in the memory.

Optionally, there may also be one or more memories in the chip system. The memory may be integrated with the processor, or may be disposed separately from the processor. This is not limited in this application. For example, the memory may be a non-transitory processor, for example, a read-only memory ROM. The memory and the processor may be integrated into a same chip, or may be separately disposed on different chips. A type of the memory and a manner of disposing the memory and the processor are not specifically limited in this application.

For example, the chip system may be an FPGA, an ASIC, a system on chip (System on Chip, SoC), a CPU, an NP, a digital signal processing circuit (Digital Signal Processor, DSP), a micro controller unit (Micro Controller Unit, MCU), a programmable controller (Programmable Logic Device, PLD), or another integrated chip.

It should be understood that the steps in the foregoing method embodiments may be completed by using a hardware integrated logic circuit or instructions in a form of software in the processor. The steps of the methods disclosed with reference to embodiments of this application may be directly performed by a hardware processor, or may be performed by a combination of hardware in the processor and a software module.

An embodiment of this application further provides a computer-readable storage medium, including instructions. When the instructions are run on a computer, the computer is enabled to perform the packet scheduling method performed by the first device according to the foregoing method embodiments.

An embodiment of this application further provides a computer program product including instructions. When the computer program product is run on a computer, the computer is enabled to perform the packet scheduling method performed by the first device according to the foregoing method embodiments.

In the specification, claims, and accompanying drawings of this application, the terms "first", "second", "third", "fourth", and so on (if existent) are intended to distinguish between similar objects but do not necessarily indicate a specific order or sequence. It should be understood that the data termed in such a way are interchangeable in proper circumstances so that embodiments of the present invention described herein can be implemented in other orders than the order illustrated or described herein. In addition, the terms "include" and "have" and any other variants are intended to cover the non-exclusive inclusion. For example, a process, method, system, product, or device that includes a list of steps or units is not necessarily limited to those expressly listed steps or units, but may include other steps or units not expressly listed or inherent to such a process, method, product, or device.

For example, the described apparatus embodiments are merely examples. For example, division into the units is merely logical module division and may be other division during actual implementation.

Some or all of the units may be obtained based on actual requirements to achieve the objectives of the solutions of embodiments.

In addition, module units in embodiments of this application may be integrated into one processing unit, or each of the units may exist alone physically, or two or more units are integrated into one unit. The integrated unit may be implemented in a form of hardware, or may be implemented in a form of a software module unit.

When the integrated unit is implemented in the form of a software module unit and sold or used as an independent product, the integrated unit may be stored in a computer-readable storage medium. Based on such an understanding, the technical solutions of this application essentially, or the part contributing to a current technology, or all or some of the technical solutions may be implemented in the form of a software product. The computer software product is stored in a storage medium and includes several instructions for instructing a computer device (which may be a personal computer, a server, or a network device) to perform all or some of the steps of the methods described in embodiments of this application. The storage medium includes any medium that can store program code, such as a USB flash drive, a removable hard disk, a read-only memory (ROM, Read-Only Memory), a random access memory (RAM, Random Access Memory), a magnetic disk, or an optical disc.

A person skilled in the art should be aware that in the foregoing one or more examples, functions described in the present invention may be implemented by hardware, software, firmware, or any combination thereof. When the functions are implemented by software, the foregoing functions may be stored in a computer-readable medium or transmitted as one or more instructions or code in a computer-readable medium. The computer-readable medium includes a computer storage medium and a communication medium, where the communication medium includes any medium that enables a computer program to be transmitted from one place to another. The storage medium may be any available medium accessible to a general-purpose or a dedicated computer.

The objectives, technical solutions, and beneficial effects of the present invention are further described in detail in the foregoing specific implementations. It should be understood that the foregoing descriptions are merely specific implementations of the present invention.

Claim 1:
A packet scheduling method, wherein the method comprises:
when a quantity of remaining tokens in a first token bucket of a first device does not satisfy that a first packet is to be removed from a queue, determining (S201), by the first device, whether a length of a packet cached in the queue is less than a first threshold; and
in response to that the length of the packet cached in the queue is not less than the first threshold, issuing (S202), by the first device, a token in a second token bucket to the first packet, and removing the first packet from the queue, wherein the method is characterized by further comprising:
when the quantity of remaining tokens in the first token bucket of the first device does not satisfy that a second packet is to be removed from the queue, determining (S307), by the first device, whether the length of the packet cached in the queue is less than the first threshold; and
in response to that the length of the packet cached in the queue is less than the first threshold, keeping (S310), by the first device, the second packet in the queue before the quantity of remaining tokens in the first token bucket can satisfy that the second packet is to be removed from the queue, and
wherein after the keeping (S310) the second packet in the queue, the method further comprises:
determining (S311), by the first device, that the quantity of remaining tokens in the first token bucket satisfies that the second packet is to be removed from the queue; and
issuing (S311), by the first device, a token in the first token bucket to the second packet, and removing the second packet from the queue.