Patent Description:
Embodiments of this application relate to the field of communications technologies, and in particular, to a method and an apparatus for determining a packet dequeue rate.

A network device includes a cache. The cache may maintain a plurality of packet queues. After receiving a plurality of packets with a same feature, the network device may enqueue the plurality of packets into one of the plurality of packet queues by storing the plurality of packets in the cache.

Before sending the plurality of packets to a remote network device, the network device needs to dequeue the plurality of packets from the packet queue. After determining a rate at which the plurality of packets are dequeued, the network device may calculate a queuing latency (queuing latency) of a new packet based on the rate at which the plurality of packets are dequeued. Further, the network device may perform quality of service (Quality of Service, QoS)-based processing on the new packet. The new packet may be a packet received by the network device after the plurality of packets are dequeued from the packet queue.

The network device needs to calculate lengths of the plurality of packets to determine the rate at which the plurality of packets are dequeued. In specific implementation, a problem of wasting storage resources may exist. For example, the network device stores the plurality of packets in a memory <NUM>, and stores the calculated lengths of the plurality of packets in a memory <NUM>. Consequently, storage resource utilization is low. <NPL>, discusses a lightweight active queue management design that can effectively control the average queueing latency to a target value. <NPL>, discusses results of an AQM selection process and specification definition for DOCSIS <NUM> technology.

Embodiments not falling within the scope of the claims are exemplary. To improve storage resource utilization, this application provides the following solutions.

According to a first aspect, a method for determining a packet dequeue rate is provided. The method includes the following steps: allocating a plurality of consecutive blocks in a first memory to a first packet; storing the first packet and a first length in the plurality of blocks, where the first length is a length that is of a first packet queue and that is obtained when the first packet is enqueued into the first packet queue; and determining, based on a first span (span) and the first length stored in the plurality of blocks, a first rate at which a packet in the first packet queue is dequeued, where the first span is equal to a difference between a second time and a first time, the first time is a time at which the first packet is enqueued into the first packet queue, and the second time is a time at which the first packet is dequeued from the first packet queue.

A length of the first packet is less than capacities of the plurality of consecutive blocks. Utilization of the plurality of blocks is low if the plurality of blocks are used to store only the first packet. In the foregoing technical solution, both the first packet and the length (namely, the first length) that is of the first packet queue and that is obtained when the first packet is enqueued into the first packet queue are stored in the plurality of blocks in the first memory. Another storage resource does not need to be allocated to the first length. For example, a memory other than the first memory does not need to be used to store the first length. Therefore, in the foregoing technical solution, storage resources are saved, and utilization of the first memory is improved.

In addition, the plurality of blocks are consecutive. During access to the first memory, there is a relatively small quantity of access requests required to access the consecutive blocks in the first memory, and access efficiency is high. Therefore, in the foregoing technical solution, this helps improve memory access efficiency and reduce access overheads.

In addition, in the foregoing technical solution, the first rate at which the packet is dequeued is determined based on the first length stored in the plurality of blocks. During determining of the first length, each packet that is dequeued in the first span does not need to be monitored. At least one packet is dequeued from the first packet queue in the first span. When a plurality of packets are dequeued in the first span, lengths of the packets that are dequeued in the first span do not need to be accumulated.

Therefore, according to the method for determining a packet dequeue rate provided in this solution, memory access efficiency is improved, and occupation of storage resources is reduced.

In a possible design, all of the plurality of blocks have a same capacity, and a difference between a length of the first packet and capacities of the plurality of blocks is less than the capacity of one of the plurality of blocks.

In the foregoing technical solution, the difference between the length of the first packet and the capacities of the plurality of blocks is less than the capacity of one of the plurality of blocks. The foregoing description means that each block needs to be used when the first packet is stored in the first memory. After the first packet is stored in the plurality of blocks, there is no completely idle block in the plurality of blocks. Therefore, in the foregoing technical solution, this helps further save storage resources and improve storage resource utilization.

In a possible design, the method further includes the following steps: determining a queuing latency of a second packet at a third time based on the first rate, where the queuing latency is equal to a quotient of a second length and the first rate, the second length is a length of the first packet queue at the third time, and the third time is later than the second time; and processing the second packet based on the queuing latency.

In the foregoing technical solution, the queuing latency of the second packet may be determined by using the first rate, and the second packet is processed by using the queuing latency. The foregoing description means that the second packet is processed based on the queuing latency of the second packet. Therefore, this helps improve efficiency of processing the second packet.

In a possible design, the processing the second packet based on the queuing latency includes the following step: when the queuing latency is less than a first threshold, enqueuing the second packet into the first packet queue by storing the second packet in a second memory, where a working frequency of the second memory is higher than a working frequency of the first memory.

In the foregoing technical solution, when the queuing latency of the second packet is relatively short, the second packet is enqueued into a memory with a relatively high working frequency. The second packet stays in a high-speed memory for a relatively short time, so that a resource of the high-speed memory is properly used, and a speed of processing the second packet is improved.

In a possible design, the processing the second packet based on the queuing latency includes the following step: when the queuing latency is greater than a first threshold and less than a second threshold, enqueuing the second packet into the first packet queue by storing the second packet in the first memory.

In a possible design, the processing the second packet based on the queuing latency includes the following step: when the queuing latency is greater than a second threshold, avoiding enqueuing the second packet into the first packet queue.

When the queuing latency of the second packet is relatively high, the second packet is prevented from being enqueued into the first packet queue. The relatively high queuing latency of the second packet means that network congestion occurs. In this case, network congestion may deteriorate if the second packet is enqueued into the packet queue. Therefore, avoiding enqueuing the second packet into the first packet queue helps avoid network congestion deterioration. In addition, this helps reduce occupation of storage resources by a packet with a relatively high queuing latency, to save the storage resources.

In a possible design, the processing the second packet based on the queuing latency includes the following step: when the queuing latency is greater than a third threshold, performing an explicit congestion notification marking (explicit congestion notification marking, ECN marking) on the second packet.

When the queuing latency of the second packet is relatively high, ECN marking is performed on the second packet. The relatively high queuing latency of the second packet means that network congestion occurs. A receiver of the second packet may indicate, based on ECN marking performed on the second packet, a sender of the second packet to reduce a packet sending rate. Therefore, this helps reduce network congestion.

In a possible design, the method further includes the following step: storing the first time in the first memory.

The determining, based on a first span and the first length stored in the plurality of blocks, a first rate at which a packet in the first packet queue is dequeued includes the following step: determining, based on the first length stored in the plurality of blocks and the first time stored in the first memory, the first rate at which the packet in the first packet queue is dequeued.

In a possible design, the method further includes the following step: determining, based on the second length and a second span, a second rate at which the packet in the first packet queue is dequeued, where the second length is a length that is of the first packet queue and that is obtained when a third packet is enqueued into the first packet queue, the second span is equal to a difference between a fifth time and a fourth time, the fourth time is a time at which the third packet is enqueued into the first packet queue, the fifth time is a time at which the third packet is dequeued from the first packet queue, and the second length is greater than <NUM>.

The third packet and the first packet are not adjacent to each other in the first packet queue. Alternatively, the third packet and the first packet are adjacent to each other in the first packet queue.

A rate at which the packet in the first packet queue is dequeued may change with a time. Therefore, the rate at which the packet in the first packet queue is dequeued needs to be re-determined. A rate at which the packet in the first packet queue is dequeued when the first packet is dequeued can be relatively accurately estimated by using a rate determined based on the length that is of the first packet queue and that is obtained when the first packet is enqueued. A rate at which the packet in the first packet queue is dequeued when the third packet is dequeued can be relatively accurately estimated by using a rate determined based on the length that is of the first packet queue and that is obtained when the third packet is enqueued. When the first packet and the third packet are adjacent to each other, a time at which the first packet is dequeued is relatively close to a time at which the third packet is dequeued. Therefore, a difference between the first rate and the second rate may be relatively small. When the first packet and the third packet are not adjacent to each other, a time at which the first packet is dequeued is not close to a time at which the third packet is dequeued. Therefore, a difference between the first rate and the second rate may be relatively large.

According to a second aspect, an apparatus for determining a packet dequeue rate is provided. The apparatus includes an allocation unit, a storage unit, and a first determining unit. The allocation unit is configured to allocate a plurality of consecutive blocks in a first memory to a first packet. The storage unit is configured to store the first packet and a first length in the plurality of blocks, where the first length is a length that is of a first packet queue and that is obtained when the first packet is enqueued into the first packet queue. The first determining unit is configured to determine, based on a first span and the first length stored in the plurality of blocks, a first rate at which a packet in the first packet queue is dequeued, where the first span is equal to a difference between a second time and a first time, the first time is a time at which the first packet is enqueued into the first packet queue, and the second time is a time at which the first packet is dequeued from the first packet queue.

In a possible design, the apparatus further includes a second determining unit and a processing unit.

The second determining unit is configured to determine a queuing latency of a second packet at a third time based on the first rate, where the queuing latency is equal to a quotient of a second length and the first rate, the second length is a length of the first packet queue at the third time, and the third time is later than the second time.

The processing unit is configured to process the second packet based on the queuing latency.

In a possible design, the processing unit is configured to: when the queuing latency is less than a first threshold, enqueue the second packet into the first packet queue by storing the second packet in a second memory, where a working frequency of the second memory is higher than a working frequency of the first memory.

In a possible design, the processing unit is configured to: when the queuing latency is greater than a first threshold and less than a second threshold, enqueue the second packet into the first packet queue by storing the second packet in the first memory.

In a possible design, the processing unit is configured to: when the queuing latency is greater than a second threshold, avoid enqueuing the second packet into the first packet queue.

In a possible design, the processing unit is configured to: when the queuing latency is greater than a third threshold, perform explicit congestion notification marking on the second packet.

In a possible design, the storage unit is further configured to store the first time in the first memory. The first determining unit is configured to determine, based on the first length stored in the plurality of blocks and the first time stored in the first memory, the first rate at which the packet in the first packet queue is dequeued.

In a possible design, the apparatus further includes a third determining unit. The third determining unit is configured to determine, based on the second length and a second span, a second rate at which the packet in the first packet queue is dequeued, where the second length is a length that is of the first packet queue and that is obtained when a third packet is enqueued into the first packet queue, the second span is equal to a difference between a fifth time and a fourth time, the fourth time is a time at which the third packet is enqueued into the first packet queue, the fifth time is a time at which the third packet is dequeued from the first packet queue, and the second length is greater than <NUM>.

According to a third aspect, an apparatus is provided. The apparatus may be configured to perform the method provided in any one of the first aspect or the possible designs of the first aspect. The apparatus includes a processor and a memory coupled to the processor. The memory stores a computer program. When the processor executes the computer program, the apparatus is enabled to perform the method provided in any one of the first aspect or the possible designs of the first aspect.

According to a fourth aspect, a computer readable storage medium is provided. The computer readable storage medium is configured to store a computer program. When the computer program is executed, a computer may be enabled to perform the method provided in any one of the first aspect or the possible designs of the first aspect.

In a possible design, the computer readable storage medium may be a non-volatile computer readable storage medium.

In a possible design, the computer may be a network apparatus.

In a possible design, the network apparatus may be a forwarding apparatus. The forwarding apparatus may be a router, a network switch, a firewall, or a load balancer.

According to a fifth aspect, a computer program product is provided. The computer program product includes a computer program. When the computer program is executed, a computer may be enabled to perform the method provided in any one of the first aspect or the possible designs of the first aspect.

To describe the technical solutions in the embodiments of this application more clearly, the following briefly describes the accompanying drawings required for describing the embodiments. It is clear that the accompanying drawings in the following description show merely some embodiments in this application. A person of ordinary skill in the art may derive other drawings from these accompanying drawings without creative efforts.

In the data communications field, a packet may arrive at a destination after being forwarded by a plurality of forwarding apparatuses. The forwarding apparatus may be a router. The router may forward an internet protocol (internet protocol, IP) packet. The forwarding apparatus may be a network switch. The network switch may forward an Ethernet frame.

<FIG> is a networking structural diagram according to this application. Referring to <FIG>, the networking structural diagram includes seven routers: a router <NUM> to a router <NUM>. Each router may include a plurality of physical interface cards. Each physical interface card may include a plurality of ports. <FIG> shows two egress ports (a first egress port and a second egress port) in the router <NUM> and two egress ports (a third egress port and a fourth egress port) in the router <NUM>. The router <NUM> is connected to the router <NUM> through the first egress port. The router <NUM> is connected to the router <NUM> through the second egress port. The router <NUM> is connected to the router <NUM> through the third egress port. The router <NUM> is connected to the router <NUM> through the fourth egress port.

When the router <NUM> receives a packet, the router <NUM> determines an egress port used to forward the packet, for example, the first egress port, and forwards the packet through the first egress port. When the router <NUM> receives the packet forwarded by the router <NUM>, the router <NUM> determines an egress port used to forward the packet, for example, the third egress port, and forwards the packet through the third egress port.

<FIG> is a possible schematic structural diagram of the router <NUM> in <FIG>. Another router (for example, the router <NUM>) in <FIG> may also be the schematic structural diagram shown in <FIG>.

Referring to <FIG>, the router <NUM> includes a control board <NUM>, a switch fabric unit <NUM>, an interface board <NUM>, and an interface board <NUM>. The control board <NUM> includes a central processing unit <NUM>. The control board <NUM> may be configured to perform a routing protocol. The routing protocol may be a border gateway protocol (border gateway protocol, BGP) or an interior gateway protocol (interior gateway protocol, IGP). The control board <NUM> may generate a routing table by performing the routing protocol, and send the routing table to the interface boards <NUM> and <NUM>. It should be noted that the router <NUM> in <FIG> may also use a structure different from the structure shown in <FIG>. For example, the router <NUM> in <FIG> may include only one control board and one interface board, but does not include a switch fabric unit. Certainly, the router <NUM> in <FIG> may include more than two interface boards. When the router <NUM> includes only one interface board but does not include a switch fabric unit, an IP packet received through an ingress port of the interface board may be sent from an egress port of the interface board after being processed by the interface board. When the router <NUM> includes a plurality of interface boards and includes a switch fabric unit, an IP packet received through an ingress port of an interface board of the router <NUM> may be sent from an egress port of another interface board of the router <NUM> after being processed by the switch fabric unit. Specific structures of the router <NUM> and another router in <FIG> are not limited in this application.

The interface board <NUM> may forward an IP packet by searching the routing table. Specifically, the interface board <NUM> includes a central processing unit <NUM>, a network processor <NUM>, a physical interface card <NUM>, and a memory <NUM>. It should be noted that <FIG> does not show all components that can be included in the interface board <NUM>. In specific implementation, the interface board <NUM> may further include another component. For example, the interface board <NUM> may further include a traffic manager, so that the interface board <NUM> has queue scheduling and management functions. In addition, the interface board <NUM> may further include an ingress fabric interface chip (ingress fabric interface chip, iFIC), so that a packet from the interface board <NUM> can be switched to the interface board <NUM> through the switch fabric unit <NUM>. For a specific implementation of the interface board <NUM> including the traffic manager and the iFIC, refer to <FIG> and corresponding descriptions. The central processing unit <NUM> may receive a routing table sent by the central processing unit <NUM>, and store the routing table in the memory <NUM>. The physical interface card <NUM> may be configured to receive an IP packet sent by the router <NUM>. The network processor <NUM> may search the routing table in the memory <NUM> for a routing entry that matches the IP packet received by the physical interface card <NUM>, and send the IP packet to the switch fabric unit <NUM> based on the matched routing entry. The switch fabric unit <NUM> may be configured to switch an IP packet from one interface board to another interface board. For example, the switch fabric unit <NUM> may switch the IP packet from the interface board <NUM> to the interface board <NUM>. Specifically, the switch fabric unit <NUM> may switch the IP packet from the interface board <NUM> to the interface board <NUM> through cell switching. For example, the network processor <NUM> may obtain a destination IP address in the IP packet. The network processor <NUM> may search, based on a longest prefix matching algorithm, the routing table for the routing entry that matches the IP packet, and determine an egress port based on the routing entry that matches the IP packet. The routing entry that matches the IP packet includes an identifier of the egress port. Before the IP packet sent by the network processor <NUM> to the switch fabric unit <NUM> arrives at the switch fabric unit <NUM>, the interface board <NUM> may perform queue scheduling and management on the IP packet. Specifically, the interface board <NUM> may perform queue scheduling and management on the IP packet by using a traffic manager <NUM> in <FIG>.

The interface board <NUM> may forward the IP packet by searching the routing table. The interface board <NUM> includes a central processing unit <NUM>, a network processor <NUM>, a physical interface card <NUM>, and a memory <NUM>. <FIG> does not show all components that can be included in the interface board <NUM>. In specific implementation, the interface board <NUM> may further include another component. For example, the interface board <NUM> may further include a traffic manager, so that the interface board <NUM> has queue scheduling and management functions. In addition, the interface board <NUM> may further include an egress fabric interface chip (egress fabric interface chip, eFIC), so that the interface board <NUM> can correctly receive a packet from the interface board <NUM> through the switch fabric unit <NUM>. For a specific implementation of the interface board <NUM> including the traffic manager and the eFIC, refer to <FIG> and corresponding descriptions. The central processing unit <NUM> may receive a routing table sent by the central processing unit <NUM>, and store the routing table in the memory <NUM>. The network processor <NUM> may be configured to receive an IP packet from the switch fabric unit <NUM>. The IP packet from the switch fabric unit <NUM> may be the IP packet that is sent by the router <NUM> and that is received by the physical interface card <NUM>. The network processor <NUM> may search the routing table in the memory <NUM> for a routing entry that matches the IP packet from the switch fabric unit <NUM>, and send the IP packet to the physical interface card <NUM> based on the matched routing entry. The physical interface card <NUM> may be configured to send an IP packet to the router <NUM>. Before the IP packet sent by the network processor <NUM> to the physical interface card <NUM> arrives at the physical interface card <NUM>, the interface board <NUM> may perform queue scheduling and management on the IP packet. Specifically, the interface board <NUM> may perform queue scheduling and management on the IP packet by using a traffic manager <NUM> in <FIG>.

A plurality of packets need to be transmitted in a network, and times of sending the packets may be different. The router includes a memory, to reduce disorder of the packets to be transmitted in the network. The memory may be a first in first out memory (first in first out memory). The router may perform queue scheduling and management on a to-be-forwarded packet by using the memory. In addition, the router may receive a large quantity of packets in a short time, and a congestion degree of a first in first out queue in the memory in the router may be relatively high due to the large quantity of packets. The router may perform discard management on a packet enqueued into the first in first out queue, to reduce the congestion degree of the first in first out queue.

<FIG> is a schematic structural diagram of the interface board <NUM> shown in <FIG> in a possible implementation. Referring to <FIG>, the interface board <NUM> includes the network processor (network processor, NP) <NUM>, the traffic manager (traffic manager, TM) <NUM>, a memory <NUM>, and an iFIC <NUM>. It should be noted that <FIG> shows only some components included in the interface board <NUM>. In specific implementation, the interface board <NUM> shown in <FIG> may further include the component in the interface board <NUM> shown in <FIG>. The interface board shown in <FIG> can perform queue scheduling and management on uplink traffic. The uplink traffic may be traffic that is received by the interface board <NUM> through the physical interface card <NUM> and that is to be sent to the switch fabric unit <NUM>. Specifically, after being processed by the network processor <NUM> and the traffic manager <NUM>, a packet received through the physical interface card <NUM> is sent to the ingress fabric interface chip <NUM>. After the ingress fabric interface chip <NUM> receives the packet sent by the traffic manager <NUM>, the ingress fabric interface chip <NUM> may generate a plurality of cells based on the packet, and send the plurality of cells to the switch fabric unit <NUM>. The processing performed by the traffic manager <NUM> on the packet may include enqueue processing and dequeue processing. For example, the traffic manager <NUM> may perform enqueue processing on the packet by storing the packet in the memory <NUM>. The traffic manager <NUM> may perform dequeue processing on the packet by deleting the packet stored in the memory <NUM>. The memory <NUM> may be configured to: store and maintain a packet queue. The packet queue includes a plurality of packets. The packet queue may be a first in first out queue. The memory <NUM> may be a first in first out memory. The traffic manager <NUM> can perform enqueue management on a packet that is to enter the packet queue, and perform dequeue management on a packet that is to leave the packet queue. Specifically, the traffic manager <NUM> can store and maintain a packet descriptor queue. The packet descriptor queue includes a plurality of packet descriptors. The plurality of packets included in the packet queue are in a one-to-one correspondence with the plurality of packet descriptors included in the packet descriptor queue. Each packet descriptor is used to indicate information about a corresponding packet. For example, the packet descriptor may include a storage location of the packet corresponding to the packet descriptor in the memory <NUM>. In addition, the packet descriptor may further include a time at which the packet corresponding to the packet descriptor enters the router <NUM>. Specifically, the time at which the packet corresponding to the packet descriptor enters the router <NUM> may be a time at which the packet corresponding to the packet descriptor is received by the physical interface card <NUM>. In addition, the packet descriptor may further include a length that is of the packet queue and that is obtained when the packet corresponding to the packet descriptor is enqueued into the packet queue. For example, when a packet <NUM> is enqueued into a packet queue <NUM>, the packet queue <NUM> includes a packet <NUM>, a packet <NUM>, and a packet <NUM>. The packet <NUM> includes <NUM> bits, the packet <NUM> includes <NUM> bits, and the packet <NUM> includes <NUM> bits. Therefore, when the packet <NUM> is enqueued into the packet queue <NUM>, a length of the packet queue <NUM> is <NUM> bits. It can be learned that when the packet <NUM> is enqueued into the packet queue <NUM>, the packet queue <NUM> does not include the packet <NUM>. The traffic manager <NUM> can perform enqueue management on the packet from the network processor <NUM>. For example, the traffic manager <NUM> may determine, based on a WRED algorithm, whether to discard the packet from the network processor <NUM>. Certainly, the traffic manager <NUM> may alternatively determine, based on another algorithm, whether to discard the packet from the network processor <NUM>. If the traffic manager <NUM> determines not to discard the packet from the network processor <NUM>, the traffic manager <NUM> may store the packet in the packet queue in the memory <NUM>. Specifically, the traffic manager <NUM> may store the packet at a queue tail of the packet queue in the memory <NUM>. In addition, the traffic manager <NUM> generates, based on the storage location of the packet in the memory <NUM>, a packet descriptor corresponding to the packet, and stores the packet descriptor in a packet descriptor queue. Specifically, the traffic manager <NUM> may store the packet descriptor at a queue tail of the packet descriptor queue. The packet descriptor queue may be stored in the traffic manager <NUM>. Specifically, the packet descriptor queue may be stored in a queue manager in the traffic manager. For details, refer to <FIG> and related descriptions in <FIG> in the embodiment. The traffic manager <NUM> can perform dequeue management on the packet queue stored in the memory <NUM>. For example, when the traffic manager <NUM> determines, through weighted fair queuing (weighted fair queuing, WFQ), that a packet in the packet queue stored in the memory <NUM> needs to be sent, the traffic manager <NUM> may send a scheduling signal to the memory <NUM> based on a queue head of the packet descriptor queue. Certainly, the traffic manager <NUM> may alternatively determine, based on another queue scheduling algorithm, that a packet in the packet queue stored in the memory <NUM> needs to be sent. The scheduling signal includes a storage location of a packet located at a queue head of the packet queue. The scheduling signal is used to indicate the memory <NUM> to provide the traffic manager <NUM> with the packet located at the queue head of the packet queue. The memory <NUM> provides the traffic manager <NUM> with the packet located at the queue head of the packet queue, and deletes the sent packet from the packet queue. The traffic manager <NUM> obtains, from the memory <NUM>, the packet located at the queue head of the packet queue, and sends the packet to the ingress fabric interface chip <NUM>. After the traffic manager <NUM> sends the packet to the ingress fabric interface chip <NUM>, the traffic manager <NUM> deletes a packet descriptor corresponding to the sent packet from the packet descriptor queue. In the foregoing examples, the packet queue is stored in the memory <NUM>. The memory <NUM> may include a plurality of blocks. The plurality of blocks may be consecutive. The plurality of blocks may have a same capacity. For example, the plurality of blocks may be a plurality of cache lines (cache line, CL). A capacity of each cache line may be <NUM> bits. The traffic manager <NUM> may include a storage controller. The traffic manager <NUM> may access the memory <NUM> by using the storage controller. For example, a length of the packet <NUM> is <NUM> bits. The length of the packet <NUM> is greater than capacities of two cache lines, and is less than capacities of three cache lines. When the traffic manager <NUM> needs to perform enqueue processing on the packet <NUM>, the storage controller may perform a write operation on the three consecutive cache lines. The capacities of the three consecutive cache lines are <NUM> bits. The three consecutive cache lines may be respectively a CL <NUM>, a CL <NUM>, and a CL <NUM>. The storage controller may perform a write operation on the CL <NUM>, the CL <NUM>, and the CL <NUM>, to enqueue the packet <NUM> into the packet queue <NUM>. It should be noted that the memory <NUM> may include more or fewer cache lines. For example, the memory <NUM> may further include a CL <NUM> and a CL <NUM>. When the packet <NUM> is enqueued into the packet queue <NUM>, the length of the packet queue <NUM> is <NUM> bits. <NUM> in decimal notation may be represented as a <NUM>-bit binary number. A computer needs to use <NUM>-bit storage space to store <NUM> in decimal notation. Specifically, <NUM> in decimal notation is <NUM> in binary notation. The foregoing description means that when the storage controller writes the length of the packet queue <NUM> to the memory <NUM>, the length of the packet queue <NUM> needs to occupy <NUM>-bit storage space of the memory <NUM>. The packet <NUM> occupies <NUM>-bit storage space of the memory <NUM>. <NUM>-bit storage space is required to store the packet <NUM> and the length of the packet queue <NUM>. The capacities of the CL <NUM>, the CL <NUM>, and the CL <NUM> are <NUM> bits. Therefore, the packet <NUM> and the length of the packet queue <NUM> may be stored in the CL <NUM>, the CL <NUM>, and the CL <NUM>.

In a possible design, the packet queue may be stored in the traffic manager <NUM>. Specifically, the traffic manager <NUM> may include a storage medium. The traffic manager <NUM> may perform enqueue processing on the packet by performing a write operation on the storage medium. The traffic manager <NUM> may perform dequeue processing on the packet by performing a read operation on the storage medium. For a specific implementation in which the traffic manager <NUM> performs enqueue processing and dequeue processing on the packet by using the storage medium, refer to the foregoing description that the traffic manager <NUM> performs enqueue processing and dequeue processing on the packet by using the memory <NUM>. In a possible design, a working frequency of the traffic manager <NUM> is higher than a working frequency of the memory <NUM>. The memory <NUM> may be referred to as a low-speed memory, and the storage medium included in the traffic manager <NUM> may be referred to as a high-speed memory. A working frequency of the high-speed memory is higher than a working frequency of the low-speed memory. In addition, the traffic manager <NUM> may maintain a plurality of packet queues. For example, the traffic manager <NUM> may maintain a high-priority queue by using the storage medium, and maintain a low-priority queue by using the memory <NUM>. The working frequency of the high-speed memory is higher than the working frequency of the low-speed memory, and a span in which a packet in the high-priority queue stays in the packet queue may be shorter than a span in which a packet in the low-priority queue stays in the packet queue.

In addition to the traffic manager <NUM> and the memory <NUM>, the interface board <NUM> may further include another circuit having a storage function. For example, the interface board <NUM> may further include the memory <NUM>. The memory <NUM> and the memory <NUM> have different functions. The memory <NUM> is configured to store a routing table. The network processor searches the routing table by accessing the memory <NUM>. The memory <NUM> is configured to store a first in first out queue. The traffic manager <NUM> manages the first in first out queue by accessing the memory <NUM>. The memory <NUM> and the memory <NUM> may be relatively independent memories. In a possible implementation, the memory <NUM> and the memory <NUM> may be included in one chip.

<FIG> is a schematic structural diagram of the interface board <NUM> shown in <FIG> in a possible implementation. Referring to <FIG>, the interface board <NUM> includes the network processor <NUM>, the traffic manager <NUM>, a memory <NUM>, the physical interface card <NUM>, and an eFIC <NUM>. It should be noted that <FIG> shows only some components included in the interface board <NUM>. In specific implementation, the interface board <NUM> shown in <FIG> may further include the component in the interface board <NUM> shown in <FIG>. The interface board shown in <FIG> can perform queue scheduling and management on downlink traffic. The downlink traffic may be traffic that is received by the interface board <NUM> through the switch fabric unit <NUM> and that is to be sent to the physical interface card <NUM>. After receiving the downlink traffic, the physical interface card <NUM> may send the downlink traffic to the router <NUM> through a third egress port. After the egress fabric interface chip <NUM> receives the plurality of cells from the switch fabric unit <NUM>, the egress fabric interface chip <NUM> can generate a packet based on the plurality of cells, and send the packet to the network processor <NUM>. The traffic manager <NUM> may perform discard management on the packet received by the network processor <NUM>. The traffic manager <NUM> may perform enqueue management on the packet received by the network processor <NUM>. Specifically, the received packet is placed in a packet queue in the memory <NUM> based on a scheduling algorithm, for example, placed at a queue tail of the packet queue. The traffic manager <NUM> may perform dequeue management on the packet queue stored in the memory <NUM>. The packet queue may be a first in first out queue. The memory <NUM> may be a first in first out memory. After the traffic manager <NUM> obtains a packet in the packet queue stored in the memory <NUM>, the traffic manager <NUM> may send the obtained packet to the physical interface card <NUM>. The physical interface card <NUM> may send the packet to the router <NUM> through the third egress port. For a specific implementation in which the interface board shown in <FIG> performs queue scheduling and management, refer to the description in the embodiment corresponding to <FIG>.

<FIG> is a schematic flowchart of a method for determining a packet dequeue rate according to this application. Referring to <FIG>, the method includes S501, S502, and S503. For example, the method shown in <FIG> may be performed by the interface board <NUM> shown in <FIG>. Specifically, the method may be performed by the traffic manager <NUM>, to determine a packet dequeue rate. In a possible design, the traffic manager <NUM> may be implemented by using a traffic manager <NUM> shown in <FIG>. In a possible design, the method shown in <FIG> may be performed by the interface board <NUM> shown in <FIG>. Specifically, the method may be performed by the traffic manager <NUM>. Certainly, the method shown in <FIG> may alternatively be performed by another software and hardware system.

<FIG> is a schematic structural diagram of a traffic manager <NUM> according to this application. Referring to <FIG>, the traffic manager <NUM> includes a communications interface <NUM>, a storage controller <NUM>, a communications interface <NUM>, a subtractor <NUM>, and a divider <NUM>. The communications interface <NUM> is coupled to the storage controller <NUM>. The storage controller <NUM> is coupled to the subtractor <NUM> and the divider <NUM>. The communications interface <NUM> is coupled to the subtractor <NUM>. The subtractor <NUM> is coupled to the divider <NUM>. It should be noted that <FIG> does not show all components included in the traffic manager <NUM>. In addition to the components shown in <FIG>, the traffic manager <NUM> may further include other components. For example, the traffic manager <NUM> may further include a processing circuit and a storage circuit coupled to the processing circuit. The storage circuit includes a computer program. The processing circuit may perform some functions by executing the computer program in the storage circuit. In a possible design, the subtractor <NUM> and the divider <NUM> may be implemented by executing the computer program by the processing circuit.

S501: Allocate a plurality of consecutive blocks in a first memory to a first packet.

For example, all of the plurality of consecutive blocks may have a same capacity. In a possible design, at least two of the plurality of consecutive blocks may have different capacities. Referring to the foregoing embodiment, the first packet may be a packet <NUM>. The traffic manager <NUM> may obtain the packet <NUM> through the communications interface <NUM>. Specifically, the communications interface <NUM> obtains the packet <NUM> from the network processor <NUM>. The first memory may be the memory <NUM>. The memory <NUM> may include a plurality of storage units. The plurality of storage units may include a CL <NUM>, a CL <NUM>, a CL <NUM>, a CL <NUM>, and a CL <NUM>. The CL <NUM> is adjacent to the CL <NUM>. The CL <NUM> is adjacent to the CL <NUM>. The CL <NUM> is adjacent to the CL <NUM>. The CL <NUM> is adjacent to the CL <NUM>. The traffic manager <NUM> may store identifiers of the plurality of storage units. For example, the traffic manager <NUM> may store an address of each of the plurality of storage units. In addition, the traffic manager <NUM> may store a capacity of each of the plurality of storage units. Each of the plurality of storage units may be a block. The plurality of consecutive blocks may be the CL <NUM>, the CL <NUM>, and the CL <NUM>. A length of the packet <NUM> may be <NUM> bits. A capacity of each of the plurality of consecutive blocks is <NUM> bits. The traffic manager <NUM> may determine, based on the length of the packet <NUM> and the capacity of the block in the memory <NUM>, the plurality of consecutive blocks required to store the packet <NUM>. Capacities of the plurality of consecutive blocks are greater than the length of the packet <NUM>, so that the packet <NUM> can be stored in the plurality of consecutive blocks. When capacities of all blocks in the memory <NUM> are the same, the processing circuit may determine, by executing the computer program in the storage circuit, that at least three blocks are required to store the packet <NUM>. Further, the processing circuit may allocate three consecutive storage units to the packet <NUM> based on the stored identifiers of the plurality of storage units. For example, the traffic manager <NUM> may allocate the CL <NUM>, the CL <NUM>, and the CL <NUM> to the packet <NUM>. Certainly, the traffic manager <NUM> may alternatively allocate the CL <NUM>, the CL <NUM>, and the CL <NUM> to the packet <NUM>. In a possible design, the traffic manager <NUM> may allocate four consecutive storage units or more storage units to the packet <NUM> based on the stored identifiers of the plurality of storage units. For example, the traffic manager <NUM> may allocate the CL <NUM>, the CL <NUM>, the CL <NUM>, and the CL <NUM> to the packet <NUM>. The traffic manager <NUM> may alternatively allocate the CL <NUM>, the CL <NUM>, the CL <NUM>, and the CL <NUM> to the packet <NUM>.

S502: Store the first packet and a first length in the plurality of blocks.

The first length is a length that is of a first packet queue and that is obtained when the first packet is enqueued into the first packet queue, and the first length is greater than <NUM>.

The traffic manager <NUM> may maintain the length of the first packet queue. The traffic manager <NUM> may record a current value of the length of the first packet queue by using a register. A default value of the length of the first packet queue may be <NUM>. For example, when no packet is enqueued into the first packet queue, the traffic manager <NUM> may determine that the length of the first packet queue is <NUM>. When a packet is enqueued into the first packet queue, or a packet is dequeued from the first packet queue, the traffic manager <NUM> correspondingly modifies the current value of the length of the first packet queue. Specifically, when a packet is enqueued into the first packet queue, the traffic manager <NUM> may update the current value of the length of the first packet queue, where an updated length of the first packet queue is equal to a sum of the length that is of the first packet queue and that is obtained before the update and a length of the enqueued packet. When the packet is dequeued from the first packet queue, the traffic manager <NUM> may update the current value of the length of the first packet queue, where an updated length of the first packet queue is equal to a difference between the length that is of the first packet queue and that is obtained before the update and a length of the dequeued packet.

The traffic manager <NUM> enqueues the first packet into the first packet queue by storing the first packet in the plurality of blocks. For example, the first packet queue may be a packet queue <NUM>. When the packet <NUM> is enqueued into the packet queue <NUM>, the packet queue <NUM> does not include the packet <NUM>. For example, when the packet <NUM> is enqueued into the packet queue <NUM>, the packet queue <NUM> includes a packet <NUM>, a packet <NUM>, and a packet <NUM>. The first length may be <NUM> bits. The <NUM> bits may be represented as a <NUM>-bit binary number. Specifically, <NUM> in decimal notation is <NUM> in binary notation. Therefore, <NUM>-bit storage space needs to be occupied to store the first length.

When the plurality of blocks are the CL <NUM>, the CL <NUM>, and the CL <NUM>, the traffic manager <NUM> stores the packet <NUM> and the first length in the CL <NUM>, the CL <NUM>, and the CL <NUM>. Specifically, after obtaining the packet <NUM> from the communications interface <NUM>, the storage controller <NUM> in the traffic manager <NUM> may perform a write operation on the CL <NUM>, the CL <NUM>, and the CL <NUM> based on addresses of the CL <NUM>, the CL <NUM>, and the CL <NUM>. It may be understood that after the packet <NUM> and the first length are stored in the CL <NUM>, the CL <NUM>, and the CL <NUM>, the plurality of blocks further include <NUM>-bit idle storage space. The packet <NUM> and the first length may be continuously stored in the plurality of blocks. There is no idle storage space between the packet <NUM> and the first length. The packet <NUM> and the first length may alternatively be discontinuously stored in the plurality of blocks. There is idle storage space between the packet <NUM> and the first length.

When the plurality of blocks are the CL <NUM>, the CL <NUM>, the CL <NUM>, and the CL <NUM>, the traffic manager <NUM> stores the packet <NUM> and the first length in the CL <NUM>, the CL <NUM>, the CL <NUM>, and the CL <NUM>. It may be understood that after the packet <NUM> and the first length are stored in the CL <NUM>, the CL <NUM>, the CL <NUM>, and the CL <NUM>, the plurality of blocks further include <NUM>-bit idle storage space. Specifically, the packet <NUM> may be located in the CL <NUM>, the CL <NUM>, and the CL <NUM>. The first length may be located in the CL <NUM>. Alternatively, the packet <NUM> may be located in the CL <NUM>, the CL <NUM>, and the CL <NUM>. The first length may be located in the CL <NUM>. Alternatively, the packet <NUM> may be located in the CL <NUM>, the CL <NUM>, and the CL <NUM>. The first length may be located in the CL <NUM>. Alternatively, the packet <NUM> may be located in the CL <NUM>, the CL <NUM>, and the CL <NUM>. The first length may be located in the CL <NUM>. In addition, the packet <NUM> and the first length may be continuously stored in the plurality of blocks. There is no idle storage space between the packet <NUM> and the first length. The packet <NUM> and the first length may alternatively be discontinuously stored in the plurality of blocks. There is idle storage space between the packet <NUM> and the first length.

S503: Determine, based on a first span and the first length stored in the plurality of blocks, a first rate at which a packet in the first packet queue is dequeued.

The first span is equal to a difference between a second time and a first time, the first time is a time at which the first packet is enqueued into the first packet queue, and the second time is a time at which the first packet is dequeued from the first packet queue.

For example, the first rate is equal to a quotient of the first length and the first span.

For example, the traffic manager <NUM> may be coupled to a clock circuit. For example, the traffic manager <NUM> may communicate with the clock circuit through the communications interface <NUM>. The clock circuit may be included in the control board <NUM>. The clock circuit may include a crystal oscillator and a counter. The counter may be specifically an accumulator. The counter may include a memory. A value stored in the memory is equal to a current time recorded by the clock circuit. The crystal oscillator may send a square wave to the accumulator. The square wave may include a plurality of pulse signals. Specifically, the crystal oscillator may output a pulse signal to the counter in each working period. When the counter detects a rising edge or a falling edge of the pulse signal, the counter performs an addition operation on an increment and the value stored in the memory, to update the value stored in the memory. The increment is equal to the working period of the crystal oscillator. For example, a working frequency of the crystal oscillator may be <NUM> megahertz (Mega Hertz, MHz). Correspondingly, the working period of the crystal oscillator may be <NUM> nanoseconds (nanosecond, ns).

The traffic manager <NUM> may obtain the first time and the second time by accessing the counter in the clock circuit. Specifically, when the traffic manager <NUM> enqueues the packet <NUM> into the packet queue <NUM>, the traffic manager <NUM> may obtain the first time by accessing the counter. The traffic manager <NUM> may store the first time in the memory <NUM>. When the plurality of blocks include idle storage space, the traffic manager <NUM> may store the first time in the plurality of blocks. For example, the plurality of blocks may be the CL <NUM>, the CL <NUM>, and the CL <NUM>. When the CL <NUM> includes idle storage space, the traffic manager <NUM> may store the first time in the CL <NUM>. When the traffic manager <NUM> dequeues the packet <NUM> from the packet queue <NUM>, the traffic manager <NUM> may obtain the second time by accessing the counter, and obtain the first time by accessing the CL <NUM>. Further, the traffic manager <NUM> determines the first span based on the obtained first time and second time. Specifically, the subtractor <NUM> obtains the first time from the plurality of blocks by using the storage controller <NUM>. The subtractor <NUM> obtains the second time from the counter through the communications interface <NUM>. The subtractor <NUM> uses the second time as a minuend, uses the first time as a subtrahend, and calculates a difference between the minuend and the subtrahend. The difference between the minuend and the subtrahend is equal to the first span. The traffic manager <NUM> may determine the first rate by using the divider <NUM>. Specifically, the divider <NUM> may obtain the first span from the subtractor <NUM>. The divider <NUM> obtains the first length from the plurality of blocks by using the storage controller <NUM>. The divider <NUM> may use the first length as a dividend, use the first span as a divisor, and calculate a quotient of the dividend and the divisor. The quotient of the dividend and the divisor is equal to the first rate.

In addition, in the foregoing technical solution, the first rate at which the packet is dequeued is determined based on the first length stored in the plurality of blocks. During determining of the first length, each packet that is dequeued in the first span does not need to be monitored. When a plurality of packets are dequeued in the first span, lengths of the dequeued packets do not need to be accumulated.

For example, the length of the first packet is <NUM> bits. A capacity of each of the plurality of blocks is <NUM> bits. There are three blocks. Therefore, the difference between the length of the first packet and the capacities of the plurality of blocks is equal to <NUM> bits. The <NUM> bits are less than the capacity of each block.

In a possible design, the method shown in <FIG> further includes: determining a queuing latency of a second packet at a third time based on the first rate, where the queuing latency is equal to a quotient of a second length and the first rate, the second length is a length of the first packet queue at the third time, and the third time is later than the second time; and processing the second packet based on the queuing latency.

For example, the traffic manager <NUM> may receive the second packet after determining the first rate. For example, the traffic manager <NUM> receives the second packet through the communications interface <NUM>. The second packet and the first packet may belong to a same packet flow (for example, a first packet flow). The first packet flow in this application is a plurality of packets with a same feature. At least one field in a packet header may be used to indicate a feature of the packet. For example, a plurality of IP packets with a same destination IP address may constitute the first packet flow. Based on the foregoing example, if destination IP addresses of two IP packets are different, the two IP packets belong to different packet flows, for example, respectively belong to the first packet flow and a second packet flow. For another example, a plurality of IP packets with a same destination IP address and a same source IP address may constitute the first packet flow. For another example, a plurality of IP packets with a same <NUM>-tuple may constitute the first packet flow. The <NUM>-tuple includes a source IP address, a destination IP address, a source port, a destination port, and a protocol. The source IP address, the destination IP address, and the protocol are fields in a layer <NUM> header (an IP header). The source port and the destination port are fields in a layer <NUM> header (a TCP header or a UDP header). In addition, an ingress port used to receive the packet may also be used to indicate the feature of the packet. For example, if the plurality of packets are received through a same ingress port on the physical interface card <NUM>, the plurality of packets belong to the first packet flow. If the plurality of packets are received through different ingress ports, the plurality of packets do not belong to a same packet flow. The packet in this application may be an IP packet or another packet. For example, the packet in this application may be an Ethernet frame.

It may be understood that the memory <NUM> may store and maintain only one packet queue, for example, a packet queue including the first packet flow. The memory <NUM> may alternatively store and maintain a plurality of packet queues at the same time, for example, a packet queue including the first packet flow and a packet queue including the second packet flow. In addition, priorities of the plurality of packet queues may be the same or different. When a priority of the packet queue including the first packet flow is higher than a priority of the packet queue including the second packet flow, a packet in the packet queue including the first packet flow is scheduled out of the memory <NUM> before a packet in the packet queue including the second packet flow.

The second length is the length of the first packet queue at the third time. The first packet queue does not include the second packet at the third time.

As mentioned above, the traffic manager <NUM> may further include the processing circuit and the storage circuit coupled to the processing circuit. The processing circuit is coupled to the divider <NUM>. The processing circuitry may obtain the first rate from the divider <NUM>. The storage circuit includes the computer program. The processing circuit may determine the queuing latency of the second packet by executing the computer program in the storage circuit.

The queuing latency of the second packet at the third time is used to estimate a span in which the second packet needs to stay in the first packet queue if the second packet is enqueued into the first packet queue at the third time. It should be noted that the queuing latency is not necessarily equal to a span in which the second packet actually stays in the first packet queue. The traffic manager <NUM> does not necessarily perform enqueue processing on the second packet. For example, the traffic manager <NUM> may also perform discard processing on the second packet. In addition, even if the traffic manager <NUM> enqueues the second packet into the first packet queue at the third time, a rate at which the packet in the first packet queue is dequeued may not remain at the first rate. For example, the traffic manager <NUM> may also receive a backpressure signal for the first packet queue, and the traffic manager <NUM> may reduce the rate at which the packet in the first packet queue is dequeued.

However, a case in which the queuing latency is determined based on the first rate to estimate the span in which the second packet stays in the first packet queue if the second packet is enqueued into the first packet queue is still meaningful for determining how to process the second packet.

The processing circuit in the traffic manager <NUM> may perform enqueue processing or discard processing on the second packet based on the queuing latency.

The following describes, by using an example, a case in which the second packet is processed based on the queuing latency.

Example <NUM>: When the queuing latency is less than a first threshold, the second packet is enqueued into the first packet queue by storing the second packet in a second memory, where a working frequency of the second memory is higher than a working frequency of the first memory.

For example, the first threshold is equal to <NUM> second, or <NUM> millisecond, or <NUM> microsecond. The first threshold may alternatively be equal to another value. A person skilled in the art may set the first threshold based on a capacity of the second memory. For example, if the capacity of the second memory is relatively large, the first threshold may be set to a relatively large value. If the capacity of the second memory is relatively small, the first threshold may be set to a relatively small value. The second memory may be the storage medium in the traffic manager <NUM>.

Example <NUM>: When the queuing latency is greater than a first threshold and less than a second threshold, the second packet is enqueued into the first packet queue by storing the second packet in the first memory.

For example, the first threshold is equal to <NUM> second, and the second threshold is equal to <NUM> seconds. Alternatively, the first threshold is equal to <NUM> millisecond, and the second threshold is equal to <NUM> milliseconds. Alternatively, the first threshold is equal to <NUM> microsecond, and the second threshold is equal to <NUM> microseconds. The first threshold and the second threshold each may alternatively be equal to another value. A person skilled in the art may set the first threshold and the second threshold based on capacities of the first memory and the second memory.

Example <NUM>: When the queuing latency is greater than a second threshold, the second packet is prevented from being enqueued into the first packet queue.

For example, the second threshold is equal to <NUM> seconds, <NUM> milliseconds, or <NUM> microseconds. The second threshold may alternatively be equal to another value. When the queuing latency is greater than the second threshold, the traffic manager <NUM> may perform discard processing on the second packet. Alternatively, the traffic manager <NUM> may send the second packet to the control board <NUM>. For example, the central processing unit <NUM> may process the second packet.

Example <NUM>: When the queuing latency is greater than a third threshold, ECN marking is performed on the second packet.

For example, the third threshold may be equal to <NUM> seconds, <NUM> milliseconds, or <NUM> microseconds. The third threshold may alternatively be equal to another value. The third threshold may be greater than the second threshold, or may be less than the second threshold. The traffic manager <NUM> may set a field in an IP header of the second packet. For ECN marking, refer to descriptions in RFC3168 released by the internet engineering task force (Internet Engineering Task Force, IETF). Content of related parts in this document is incorporated herein by reference in its entirety. For brevity, details are not described herein.

In a possible design, the method shown in <FIG> further includes: storing the first time in the first memory.

The determining, based on a first span and the first length stored in the plurality of blocks, a first rate at which a packet in the first packet queue is dequeued includes: determining, based on the first length stored in the plurality of blocks and the first time stored in the first memory, the first rate at which the packet in the first packet queue is dequeued.

In specific implementation, the storage controller <NUM> may obtain the first time from the clock circuit through the communications interface <NUM>. The storage controller <NUM> writes the first time to the memory <NUM>. A processor in the traffic manager <NUM> may determine the first span by executing a computer program. The processor calculates a quotient of the first length and the first span, to determine the first rate.

In a possible design, the method shown in <FIG> further includes: determining, based on the second length and a second span, a second rate at which the packet in the first packet queue is dequeued, where
the second length is a length that is of the first packet queue and that is obtained when a third packet is enqueued into the first packet queue, the second span is equal to a difference between a fifth time and a fourth time, the fourth time is a time at which the third packet is enqueued into the first packet queue, the fifth time is a time at which the third packet is dequeued from the first packet queue, and the second length is greater than <NUM>.

For example, the third packet and the first packet are not adjacent to each other in the first packet queue. Alternatively, the third packet and the first packet are adjacent to each other in the first packet queue.

For example, the second rate is equal to a quotient of the second length and the second span.

<FIG> is a schematic structural diagram of an apparatus <NUM> for determining a packet dequeue rate according to this application. The apparatus <NUM> for determining a packet dequeue rate may be configured to perform S501, S502, and S503. Referring to <FIG>, the apparatus <NUM> for determining a packet dequeue rate includes an allocation unit <NUM>, a storage unit <NUM>, and a first determining unit <NUM>.

The allocation unit <NUM> is configured to allocate a plurality of consecutive blocks in a first memory to a first packet.

The storage unit <NUM> is configured to store the first packet and a first length in the plurality of blocks, where the first length is a length that is of a first packet queue and that is obtained when the first packet is enqueued into the first packet queue.

The first determining unit <NUM> is configured to determine, based on a first span and the first length stored in the plurality of blocks, a first rate at which a packet in the first packet queue is dequeued, where
the first span is equal to a difference between a second time and a first time, the first time is a time at which the first packet is enqueued into the first packet queue, and the second time is a time at which the first packet is dequeued from the first packet queue.

Specifically, the allocation unit <NUM> may be configured to perform S501. The storage unit <NUM> may be configured to perform S502. The first determining unit <NUM> may be configured to perform S503. For specific implementations of the allocation unit <NUM>, the storage unit <NUM>, and the first determining unit <NUM>, refer to the descriptions in the embodiment shown in <FIG>.

In addition, the apparatus <NUM> for determining a packet dequeue rate may be specifically the traffic manager <NUM> shown in <FIG>. In other words, the traffic manager <NUM> may implement a function of the apparatus <NUM> for determining a packet dequeue rate.

Specifically, the allocation unit <NUM> may be implemented by using the processing circuit and the storage circuit in the traffic manager <NUM>. The storage unit <NUM> may be implemented by using the storage controller <NUM>. The first determining unit <NUM> may be implemented by using the communications interface <NUM>, the storage controller <NUM>, the subtractor <NUM>, and the divider <NUM>. For specific implementations of the allocation unit <NUM>, the storage unit <NUM>, and the first determining unit <NUM>, refer to the descriptions in the embodiment shown in <FIG>.

In a possible design, the apparatus <NUM> further includes a second determining unit and a processing unit.

The second determining unit is configured to determine a queuing latency of a second packet at a third time based on the first rate, where the queuing latency is equal to a quotient of a second length and the first rate, the second length is a length of the first packet queue at the third time, and the third time is later than the second time. The processing unit is configured to process the second packet based on the queuing latency.

The second determining unit and the processing unit may be implemented by using the processing circuit and the storage circuit in the traffic manager <NUM>. Specifically, the processing circuit may implement functions of the second determining unit and the processing unit by executing a computer program in the storage circuit.

In a possible design, the processing unit is configured to implement the following function: Specifically, when the queuing latency is less than a first threshold, the processing unit enqueues the second packet into the first packet queue by storing the second packet in a second memory, where a working frequency of the second memory is higher than a working frequency of the first memory.

In a possible design, the processing unit is configured to implement the following function: Specifically, when the queuing latency is greater than a first threshold and less than a second threshold, the processing unit enqueues the second packet into the first packet queue by storing the second packet in the first memory.

In a possible design, the processing unit is configured to implement the following function: Specifically, when the queuing latency is greater than a second threshold, the processing unit avoids enqueuing the second packet into the first packet queue.

In a possible design, the processing unit is configured to implement the following function: Specifically, when the queuing latency is greater than a third threshold, the processing unit performs ECN marking on the second packet.

In the plurality of possible designs, the processing unit may be implemented by using the processing circuit and the storage circuit in the traffic manager <NUM>. Specifically, the processing circuit may implement a function of the processing unit by executing a computer program in the storage circuit.

In a possible design, the storage unit <NUM> is further configured to store the first time in the first memory. The first determining unit <NUM> is configured to determine, based on the first length stored in the plurality of blocks and the first time stored in the first memory, the first rate at which the packet in the first packet queue is dequeued.

In a possible design, the apparatus <NUM> further includes a third determining unit. The third determining unit is configured to determine, based on the second length and a second span, a second rate at which the packet in the first packet queue is dequeued, where the second length is a length that is of the first packet queue and that is obtained when a third packet is enqueued into the first packet queue, the second span is equal to a difference between a fifth time and a fourth time, the fourth time is a time at which the third packet is enqueued into the first packet queue, the fifth time is a time at which the third packet is dequeued from the first packet queue, and the second length is greater than <NUM>.

The third determining unit may be implemented by using the processing circuit and the storage circuit in the traffic manager <NUM>. Specifically, the processing circuit may implement a function of the third determining unit by executing a computer program in the storage circuit.

<FIG> is a schematic structural diagram of an apparatus <NUM> for determining a packet dequeue rate according to this application. The apparatus <NUM> for determining a packet dequeue rate may be configured to perform the method shown in <FIG>. Referring to <FIG>, the apparatus <NUM> for determining a packet dequeue rate includes an input interface <NUM>, an output interface <NUM>, a processor <NUM>, a memory <NUM>, and a bus <NUM>. The input interface <NUM>, the output interface <NUM>, the processor <NUM>, and the memory <NUM> can communicate with each other through the bus <NUM>. The input interface <NUM> is configured to receive a packet. The output interface <NUM> is configured to send a packet. The memory <NUM> is configured to store a computer program. The processor <NUM> may perform, by accessing the computer program in the memory <NUM>, the method shown in <FIG>. For a specific implementation in which the processor <NUM> performs, by accessing the computer program in the memory <NUM>, the method shown in <FIG>, refer to the description in the embodiment shown in <FIG>.

In addition, the apparatus <NUM> for determining a packet dequeue rate may be specifically the traffic manager <NUM> shown in <FIG>. In other words, the traffic manager <NUM> may implement a function of the apparatus <NUM> for determining a packet dequeue rate. Specifically, the input interface <NUM> may be implemented by using the physical interface card <NUM>. The output interface <NUM> may be implemented by using the iFIC <NUM>. The processor <NUM> may be implemented by using a WRED circuit and a queue threshold determining circuit. For specific implementations of the input interface <NUM>, the output interface <NUM>, the processor <NUM>, and the memory <NUM>, refer to the descriptions in the embodiment shown in <FIG>.

This application further provides a computer readable storage medium. The computer readable storage medium is configured to store a computer program. When the computer program is executed, a computer may be enabled to perform the method shown in <FIG>. For details, refer to the description in the embodiment shown in <FIG>. In a possible design, the computer readable storage medium may be a non-volatile computer readable storage medium.

This application further provides a computer program product. The computer program product includes a computer program. When the computer program is executed, a computer may be enabled to perform the method shown in <FIG>. For details, refer to the description in the embodiment shown in <FIG>.

It should be understood that sequence numbers of the processes do not mean execution sequences in various embodiments of this application.

A person of ordinary skill in the art may be aware that modules and method steps in the examples described with reference to the embodiments disclosed in this specification can be implemented by electronic hardware or a combination of computer software and electronic hardware. Whether the functions are performed by hardware or a combination of computer software and electronic hardware depends on particular applications and design constraints of the technical solutions. A person skilled in the art may use different methods to implement the described functions for each particular application.

It may be clearly understood by a person skilled in the art that for the purpose of convenient and brief description, for a detailed working process of the foregoing described system, apparatus, and module, reference may be made to a corresponding process in the foregoing method embodiments.

Claim 1:
A method for determining a packet dequeue rate, comprising:
allocating (S501) a plurality of consecutive blocks in a first memory to a first packet;
storing (S502) the first packet and a first length in the plurality of blocks, wherein the first length is a length that is of a first packet queue and that is obtained when the first packet is enqueued into the first packet queue; and
determining (S503), based on a first span and the first length stored in the plurality of blocks, a first rate at which a packet in the first packet queue is dequeued, wherein the first span is equal to a difference between a second time and a first time, the first time is a time at which the first packet is enqueued into the first packet queue, and the second time is a time at which the first packet is dequeued from the first packet queue;
wherein all of the plurality of blocks have a same capacity, and a difference between a length of the first packet and capacities of the plurality of blocks is less than the capacity of one of the plurality of blocks.