Packet output controller and method for dequeuing multiple packets from one scheduled output queue and/or using over-scheduling to schedule output queues

One packet output controller includes a scheduler and a dequeue device. The scheduler performs a single scheduler operation to schedule an output queue selected from a plurality of output queues associated with an egress port. The dequeue device dequeues multiple packets from the scheduled output queue decided by the single scheduler operation. Another packet output controller includes a scheduler and a dequeue device. The scheduler performs a plurality of scheduler operations each scheduling an output queue selected from a plurality of output queues associated with an egress port. The scheduler performs a current scheduler operation, regardless of a status of a packet transmission of a scheduled output queue decided by a previous scheduler operation. The dequeue device dequeues at least one packet from the scheduled output queue decided by the current scheduler operation after the packet transmission of the scheduled output queue decided by the previous scheduler operation is complete.

BACKGROUND

The disclosed embodiments of the present invention relate to forwarding packets, and more particularly, to a packet output controller and method for dequeuing multiple packets from one scheduled output queue and/or using over-scheduling to schedule output queues.

A network switch is a computer networking device that links different electronic devices. For example, the network switch receives an incoming packet generated from a source electronic device connected to it, and transmits an outgoing packet derived from the received packet to one or more destination electronic devices for which the received packet is meant to be received. In general, the network switch has a packet buffer for buffering packet data of packets received from ingress ports, and forwards the packets stored in the packet buffer through egress ports.

Concerning ingress packets to be forwarded through the same egress port, the ingress packets come from source electronic device connected to different ingress ports. Hence, the network switch may create a plurality of output queues for ingress packets received by different ingress ports, respectively. For example, each of the output queues corresponding to the same egress port may be simply built by storing packet identifiers (packet IDs) of packets to thereby record a packet linked list indicative of an output sequence of the packets actually stored in the packet buffer. Since there are multiple output queues, a scheduler is therefore needed to perform a plurality of scheduler operations each used for making one output queue decision that indicates which output queue is granted to output one packet to the egress port.

In general, the processing time required by a single scheduler operation should be shorter than a minimum packet transmission time (e.g., a transmission time of a 64-byte packet) to achieve the desired line rate. When the line rate becomes higher, the minimum packet transmission time is shorter accordingly. For example, when the network switch is used in a 10 Gigabit Ethernet (10 GbE) environment, the minimum packet transmission time may be 67.2 ns (nanosecond); when the network switch is used in a 40 Gigabit Ethernet (40 GbE) environment, the minimum packet transmission time may be 16.8 ns; and when the network switch is used in a 100 Gigabit Ethernet (100 GbE) environment, the minimum packet transmission time may be 6.72 ns. If the packet transmission of one packet dequeued from an output queue selected by one output queue decision is already complete and the scheduler fails to make another output queue decision in time, the line rate of the egress port may decrease due to no packet transmission. Hence, regarding a high-speed network application, how to design a network switch meeting the strict scheduler timing constraint is a challenge to designers in the pertinent field.

SUMMARY

In accordance with exemplary embodiments of the present invention, a packet output controller and method for dequeuing multiple packets from one scheduled output queue and/or using over-scheduling to schedule output queues are proposed to solve the above-mentioned problem.

According to a first aspect of the present invention, an exemplary packet output controller is disclosed. The exemplary packet output controller includes a scheduler and a dequeue device. The scheduler is arranged to perform a single scheduler operation to schedule an output queue selected from a plurality of output queues associated with an egress port. The dequeue device is arranged to dequeue multiple packets from the scheduled output queue decided by the single scheduler operation.

According to a second aspect of the present invention, another exemplary packet output controller is disclosed. The exemplary packet output controller includes a scheduler and a dequeue device. The scheduler is arranged to perform a plurality of scheduler operations each scheduling an output queue selected from a plurality of output queues associated with an egress port, wherein the scheduler performs a current scheduler operation, regardless of a resultant status of a packet transmission of a scheduled output queue decided by a previous scheduler operation. The dequeue device is arranged to dequeue at least one packet from the scheduled output queue decided by the current scheduler operation after the packet transmission of the scheduled output queue decided by the previous scheduler operation is complete.

According to a third aspect of the present invention, an exemplary packet output method is disclosed. The exemplary packet output method includes: performing a single scheduler operation to schedule an output queue selected from a plurality of output queues associated with an egress port; and dequeuing multiple packets from the scheduled output queue decided by the single scheduler operation.

According to a fourth aspect of the present invention, another exemplary packet output method is disclosed. The exemplary packet output method includes: performing a plurality of scheduler operations each scheduling an output queue selected from a plurality of output queues associated with an egress port, wherein a current scheduler operation is performed, regardless of a resultant status of a packet transmission of a scheduled output queue decided by a previous scheduler operation; and after the packet transmission of the scheduled output queue decided by the previous scheduler operation is complete, dequeuing at least one packet from the scheduled output queue decided by the current scheduler operation.

DETAILED DESCRIPTION

The concept of the present invention is to release the scheduler timing constraint by dequeuing multiple packets from an output queue scheduled by a single scheduler operation and/or using over-scheduling to speed up the output queue decision-making. In this way, the packet bubble (i.e., idle egress port) probability in most cases can be reduced to thereby sustain the desired line rate. Further details of the proposed scheduling/dequeuing design are described hereinafter with reference to the accompanying drawings.

FIG. 1is a diagram illustrating a network switch according to a first embodiment of the present invention. The network switch100includes a buffer memory device102, a dequeue device104and a scheduler106. The buffer memory device102includes a packet buffer112and a queue manager114. By way of example, the packet buffer112may be implemented using a dynamic random access memory (DRAM), and the queue manager114may include static random access memories (SRAMs) to store a plurality of packet linked lists acting as a plurality of output queues115_1-115_N, respectively. When a packet is received from one of a plurality of ingress ports of the network switch100, the packet is buffered in the packet buffer112, and enqueued to one of the output queues115_1-115_N. For example, packets received from an ingress port I (not shown) and required to be forwarded through an egress port J (not shown) are enqueued to the same output queue OQI,J. For clarity and simplicity, only one egress port is shown inFIG. 1. Hence, a packet received from one of the ingress ports (e.g., port1-port N) and decided to be forwarded through the egress port is processed by a packet processor (not shown) with many lookup tables according to its packet attribute. Thus, the packet is enqueued to one of the output queues115_1-115_N maintained by the queue manager114. The scheduler106is arranged to properly schedule the output queues115_1-115_N through respective priority configurations, such as rate limitations of packets waiting to be forwarded through the same egress port. However, this is for illustrative purposes only, and is not meant to be a limitation of the present invention.

To relax the memory requirement of the output queues115_1-115_N, a linked list structure is employed to serve as one output queue. For example, each of the output queues115_1-115_N is a packet linked list composed of packet identifiers (packet IDs) of packets received from the same ingress port and required to be forwarded through the egress port. Hence, when a specific packet is dequeued from one output queue, a node which stores a packet ID of the specific packet is removed from the packet linked list, and the specific packet is read from the packet buffer112and output to the following stage (e.g., dequeue device104) for packet forwarding through the egress port.

As the packet to be forwarded through the egress port may come from any of the ingress ports, the scheduler106is arranged to perform one scheduler operation to make an output queue decision for deciding which of the output queues115_1-115_N is granted to output its packet data. That is, the scheduler106is aware of queue statuses of the output queues115_1-115_N, where the queue status of one output queue may indicate whether the output queue has packets to be serviced or not; besides, the scheduler106is arranged to properly schedule the output queues115_1-115_N that have packets waiting to be forwarded through the same egress port. After the scheduler106makes one output queue decision for granting one output queue, the scheduler106does not make the next output queue decision until an acknowledgment message ACK indicative of a resultant status of a packet transmission of the scheduled output queue is received. For example, the acknowledgement message ACK may be EmptyQ_ACK which indicates whether the scheduled output queue will become an empty queue after dequeued by the packet transmission. Thus, one scheduler operation performed by the scheduler106includes at least an operation of waiting for an acknowledgment message ACK corresponding to a packet transmission of a current winner output queue and an operation of picking a next winner output queue from a plurality of output queues. In other words, the processing time required by one scheduler operation performed by the scheduler106includes at least a wait time and a decision-making time. Hence, the scheduler decision-making operation is triggered after reception of an acknowledgement message ACK of the previous dequeue operation, and is done no later than the end of the packet transmission. To release the scheduling timing constraint, the present invention proposes dequeuing multiple packets for one scheduled output queue based on operating characteristics of the scheduler106. For example, the operating characteristics of the scheduler106may include a minimum time interval between two consecutive output queue decisions made by the scheduler106.

Please refer toFIG. 2, which is a timing diagram illustrating a first proposed solution for releasing the scheduling timing constraint according to an embodiment of the present invention. Suppose that each scheduler operation performed by the scheduler106requires the processing time equal to an A-byte packet transmission time (i.e., a transmission time of packet data with a size of A bytes), where the processing time of one single scheduler operation includes at least a wait time and a decision-making time as mentioned above. That is, in accordance with operating characteristics of the scheduler106, a minimum time interval between two consecutive output queue decisions made by the scheduler106is equal to a transmission time of packet data with a size of A bytes. At time T0, the scheduler106finishes one scheduler operation SCH0to output one output queue decision D0=OQ0, and starts the next scheduler operation SCH1(which will wait for the acknowledgement message ACK associated with packet transmission of the scheduled output queue OQ0and then make an output queue decision). After notified by a queue identifier QIDof a scheduled output queue decided by the output queue decision D0=OQ0, the dequeue device104performs a packet dequeue operation upon a scheduled output queue OQ0designated by the output queue decision D0=OQ0.

In this embodiment, the dequeue device104is allowed to dequeue multiple packets for one scheduled output queue. However, if a packet length of a single packet waiting to be dequeued from the scheduled output queue is not smaller than a threshold value (e.g., A), the dequeue device104may dequeue only one packet from the scheduled output queue since the transmission time of this long packet is able to cover the processing time required by one schedule operation for making the next output queue decision. In other words, the next output queue decision will be available at the end of the packet transmission of the current dequeued packet, such that no packet bubble (idle egress port) will happen in this case. As shown inFIG. 2, since packet length of the packet PKTmwaiting to be dequeued from the scheduled output queue OQ0is not smaller than the threshold value A, the dequeue device14only dequeues the packet PKTmfrom the scheduled output queue OQ0.

Since the transmission time of the packet PKTmis longer than the threshold value A (i.e., a minimum time interval between two consecutive output queue decisions made by the scheduler106), the scheduler operation SCH1will wait for the end of the packet transmission of the current dequeued packet PKTmafter obtaining the output queue decision D1=OQ1. At time T1, the packet transmission of the dequeued packet PKTmis complete, the scheduler106is triggered to output the output queue decision D1=OQ1and start the next scheduler operation SCH2(which will wait for the acknowledgement message ACK associated with packet transmission of the scheduled output queue OQ1and then make an output queue decision). After notified a queue identifier QIDof a scheduled output queue decided by the output queue decision D1=OQ1, the dequeue device104performs a packet dequeue operation upon a scheduled output queue OQ1designated by the output queue decision D1=OQ1.

In this embodiment, due to the fact that a packet length of a single packet PKTnwaiting to be dequeued from the scheduled output queue OQ1is smaller than the threshold value A, the transmission time of this short packet PKTnfails to cover the processing time required by one schedule operation for making the next output queue decision. Hence, the dequeue device104may dequeue more than one packet from the scheduled output queue OQ1, thus allowing the scheduler106to obtain the output queue decision D2no later than the end of the packet transmission of more than one packet. In this embodiment, a total packet length of two packets PKTnand PKTn+1waiting to be sequentially dequeued from the scheduled output queue OQ1is not smaller than the threshold value A. Therefore, the next output queue decision D2is available at the end of the packet transmission of packets PKTnand PKTn+1, such that no packet bubble (idle egress port) will happen in this case. As shown inFIG. 2, the dequeue device106would dequeue multiple packets, including PKTnand PKTn+1, from the scheduled output queue OQ1.

Since the transmission time of packets PKTnand PKTn+1is longer than the threshold value A (i.e., a minimum time interval between two consecutive output queue decisions made by the scheduler106), the scheduler operation SCH2will wait for the end of the packet transmission of the dequeued packets PKTnand PKTn+1after obtaining the output queue decision D2=OQ2. At time T2, the packet transmission of the dequeued packets PKTnand PKTn+1is complete, and the scheduler106is triggered to output the output queue decision D2=OQ2. After notified a queue identifier QIDof a scheduled output queue decided by the output queue decision D2=OQ2, the dequeue device104performs a packet dequeue operation upon a scheduled output queue OQ2designated by the output queue decision D2=OQ2.

In this embodiment, the output queue OQ2only has three packets PKTk-2, PKTk-1, PKTkwhen granted to output its packet data, where a packet length of a single packet PKTk-2waiting to be dequeued from the scheduled output queue OQ2is smaller than the threshold value A, a total packet length of multiple packets PKTk-2and PKTk-1waiting to be sequentially dequeued from the scheduled output queue OQ2is not smaller than the threshold value A, and a total packet length of all packets PKTk-2, PKTk-1, PKTkin the scheduled output queue OQ2is smaller than another threshold value 2A. If the dequeue device104merely dequeues multiple packets PKTk-2and PKTk-1from the scheduled output queue OQ2, a single short packet PKTkis left in the output queue OQ2. A packet bubble (idle egress port) may happen when the output queue OQ2is decided as a winner output queue again. To avoid this, the dequeue device104is configured to dequeue all packets PKTk-2, PKTk-1, PKTkin the scheduled output queue OQ2, thereby preventing a single short packet PKTkfrom being left in the scheduled output queue OQ2. Specifically, the dequeue device104may compare a total packet length of all packets in the scheduled output queue with a threshold value (e.g., 2A), and refer to the comparison result to decide the multiple packets to be dequeued from the scheduled output queue.

Due to the fact that a total packet length of all packets PKTk-2, PKTk-1, PKTkwaiting to be sequentially dequeued from the scheduled output queue OQ2is not smaller than the threshold value A, the transmission time of these packets PKTk-2, PKTk-1, PKTkis able to cover the processing time required by one schedule operation for making the next output queue decision. Therefore, the next output queue decision will be available before the packet transmission of all packets PKTk-2, PKTk-1, PKTk, such that no packet bubble (idle egress port) will happen in this case.

It should be noted that the output queue decisions and packets dequeued from scheduled output queues shown inFIG. 2are for illustrative purposes only, and are not meant to be limitations of the present invention. For example, any packet dequeue design that dequeues multiple packets from one scheduled output queue decided by a single scheduler operation falls within the scope of the present invention.

Please refer toFIG. 3, which is a flowchart illustrating a packet output method according to an embodiment of the present invention. Provided that the result is substantially the same, the steps are not required to be executed in the exact order shown inFIG. 3. The packet output method may be employed by the network switch100shown inFIG. 1, and may be briefly summarized as below.

Step302: Check if a current packet transmission of dequeued packet (s) is complete. If yes, go to step304; otherwise, keep checking the completion of the current packet transmission.

Step304: Output an output queue decision, and start a scheduler operation for obtaining a next output queue decision.

Step306: Check if a total packet length of all packets in a scheduled output queue indicated by the output queue decision is smaller than a threshold value 2A (i.e., Total PktL (scheduled output queue)<2A?). If yes, go to step308; otherwise, go to step310.

Step308: Dequeue all of the packets in the scheduled output queue.

Step310: Dequeue multiple packets with a total packet length not smaller than a threshold value A (i.e., ΣPktL≧A).

As a person skilled in the art can readily understand details of each step shown inFIG. 3after reading above paragraphs, further description is omitted here for brevity.

In one exemplary design, the dequeue device104is configured to dequeue multiple packets for one scheduled output queue to thereby release the scheduler timing constraint. Therefore, the scheduler106may be implemented using any conventional scheduler design. In an alternative design, the dequeue device may be implemented using any conventional dequeue design, while the scheduler is configured to employ a proposed over-scheduling scheme. The same objective of releasing the scheduler timing constraint is achieved.

Please refer toFIG. 4, which is a diagram illustrating a network switch according to a second embodiment of the present invention. The network switch400includes a dequeue device404, a scheduler406, a decision buffer device408, and the aforementioned buffer memory device102. As mentioned above, the packet to be forwarded through the egress port may come from any of the ingress ports. The scheduler406is aware of queue statuses of the output queues115_1-115_N, where the queue status of one output queue may indicate whether the output queue has packets to be serviced or not; besides, the scheduler406is arranged to perform one scheduler operation to make an output queue decision for deciding which of the output queues115_1-115_N is granted to output its buffered packet data. In this embodiment, the scheduler406performs a plurality of scheduler operations each scheduling an output queue selected from a plurality of output queues115_1-115_N associated with the same egress port, wherein the scheduler406performs a current scheduler operation, regardless of a resultant status of a packet transmission of a scheduled output queue decided by a previous scheduler operation.

As mentioned above, after the scheduler106makes one output queue decision for granting one output queue, the scheduler106does not make the next output queue decision until an acknowledgment message indicative of the resultant status of the packet transmission of the scheduled output queue is received. Thus, one scheduler operation performed by the scheduler106includes at least an operation of waiting for an acknowledgment message corresponding to a packet transmission of a current winner output queue and an operation of picking a next winner output queue from a plurality of candidate output queues. To release the scheduling timing constraint, the present invention further proposes using an over-scheduling scheme. The major difference between the schedulers106and406is that one scheduler operation performed by the scheduler406excludes an operation of waiting for an acknowledgment message corresponding to a packet transmission of a scheduled output queue. For example, the scheduler406may directly perform an operation of picking a winner output queue from a plurality of candidate output queues. In other words, the processing time required by one scheduler operation performed by the scheduler406may include a decision-making time with no wait time preceding the decision-making time. Hence, the output queue scheduling performed by the scheduler406is de-coupled from the packet dequeuing performed by the dequeue device404. That is, compared to the scheduler106, the scheduler406can operate independently and have a faster decision-making speed.

It is possible that the scheduler406outputs an output queue decision before the end of the current transmission of one dequeued packet. Hence, the decision buffer device408is implemented to buffer output queue decisions sequentially generated from the scheduler406. In this embodiment, the decision buffer device408has a single first-in first-out (FIFO) buffer410. Hence, the scheduler406may output a queue identifier QIDof a scheduled output queue decided by a current scheduler operation to the FIFO buffer410before the packet transmission of a scheduled output queue decided by a previous scheduler operation is complete. In this embodiment, the dequeue device404refers to each queue identifier read from the FIFO buffer410to dequeue a single packet from a scheduled output queue corresponding to the queue identifier.

Since the scheduler decision-making operation of the scheduler406is triggered before the acknowledgement message of the previous dequeue operation (e.g., EmptyQ_ACK), i.e., regardless of the acknowledgement message of the previous dequeue operation (e.g., EmptyQ_ACK), it is possible that an output queue with no packet to be dequeued is selected as one scheduled output queue and the queue ID thereof is stored into the FIFO buffer410. If the dequeue device404performs a dequeue operation upon this empty output queue, packet bubble (idle egress port) will occur due to no packet transmission. In this embodiment, based on the queue manager status, the decision buffer device408may cancel the decision of an empty output queue (e.g., QID_1) in the FIFO buffer410, and then select the next decision (e.g., QID_2) in the FIFO buffer410.

Please refer toFIG. 5, which is a timing diagram illustrating a second proposed solution for releasing the scheduling timing constraint according to an embodiment of the present invention. Suppose that each scheduler operation performed by the scheduler406requires the processing time equal to a B-byte packet transmission time (i.e., a transmission time of packet data with a size of B bytes), where the processing time of one single scheduler operation includes a decision-making time as mentioned above. In other words, a minimum time interval between two consecutive output queue decisions made by the scheduler406is equal to a transmission time of packet data with a size of B bytes, where B<A. At time T0, the scheduler406finishes one scheduler operation SCH0to output one output queue decision D0=OQ0, and starts the next scheduler operation SCH1. After notified a queue identifier QIDof a scheduled output queue decided by the output queue decision D0=OQ0, the dequeue device404performs a packet dequeue operation upon a scheduled output queue OQ0designated by the output queue decision D0=OQ0. In this embodiment, the dequeue device404is configured to dequeue a single packet for one scheduled output queue. As shown inFIG. 5, the dequeue device404only dequeues the packet PKTmfrom the scheduled output queue OQ0.

At time T1, the packet transmission of the dequeued packet PKTmis not complete; however, the scheduler406outputs the output queue decision D1=OQ1, and starts the next scheduler operation SCH2. At time T2, the packet transmission of the dequeued packet PKTmis complete, and the dequeue device404performs a packet dequeue operation upon the next scheduled output queue OQ1to start dequeuing the packet PKTnfrom the scheduled output queue OQ1. The dequeued packet PKTmis a long packet, such that the transmission time Time (PKTm) of the packet PKTmwith the packet length PktL(PKTm) is longer than the processing time of one single scheduler operation (i.e., B-byte packet transmission time). In a case where the next dequeued packet PKTnis a short packet, the time (Time (PKTm)−B) saved by the over-scheduling scheme allows the scheduler406to start the scheduler operation SCH2before the dequeue device404starts the packet transmission of the dequeued packet PKTndecided by the scheduler operation SCH1, which increases the probability that the scheduler106can obtain the output queue decision D2no later than the end of the packet transmission of the dequeued packet PKTn. As shown inFIG. 5, the scheduler operation SCH2outputs the output queue decision D2=OQ2at time T3(which is prior to the time T4at which the packet transmission of the dequeued packet PKTnis complete), and the dequeue device104starts dequeuing the packet PKTkfrom the scheduled output queue OQ2at time T4. In this way, no packet bubble (idle egress port) will happen in this case.

It should be noted that the output queue decisions and packets dequeued from scheduled output queues shown inFIG. 5are for illustrative purposes only, and are not meant to be limitations of the present invention. For example, any scheduler design that makes multiple output queue decisions in an over-scheduling manner falls within the scope of the present invention.

In above example shown inFIG. 4, the dequeue device404is configured to dequeue a single packet for a scheduled output queue decided by a single scheduler operation. In an alternative design, the network switch may employ the proposed over-scheduling scheme and the proposed multi-packet dequeue scheme to release the scheduler timing constraint. The optimized packet forwarding performance can be achieved by reducing the packet bubble (idle egress port) probability in most cases. Please refer toFIG. 6, which is a diagram illustrating a network switch according to a third embodiment of the present invention. The network switch600includes the aforementioned dequeue device104, scheduler406, decision buffer device408and buffer memory device102. Specifically, the network switch600is obtained by replacing the dequeue device404in the network device400with the dequeue device104shown inFIG. 1. As a person skilled in the art can readily understand operation and function of each component in the network switch600after reading above paragraphs, further description is omitted here for brevity.

Please refer toFIG. 7, which is a flowchart illustrating a packet output method according to another embodiment of the present invention. Provided that the result is substantially the same, the steps are not required to be executed in the exact order shown inFIG. 7. The packet output method may be employed by the network switch400/600, and may be briefly summarized as below.

Step702: Trigger a scheduler operation to make an output queue decision.

Step704: Store a queue identifier (ID) of a scheduled output queue decided by the output queue decision into a decision buffer device. Go to step710.

Step706: Check if a current packet transmission of dequeued packet(s) is complete. If yes, go to step708; otherwise, keep checking the completion of the current packet transmission.

Step708: Read a queue ID from the decision buffer device.

Step710: Check if the queue ID is a valid queue (i.e., a non-empty queue). If yes, go to step712; otherwise, go back to step708to select the next queue ID.

Step712: Dequeue packet(s) from the output queue corresponding to the queue ID.

As a person skilled in the art can readily understand details of each step shown inFIG. 7after reading above paragraphs, further description is omitted here for brevity.

Due to the inherent characteristics of the proposed over-scheduling scheme, there may be a performance issue. More specifically, since the scheduler406performs a current scheduler operation, regardless of a resultant status of a packet transmission of a scheduled output queue decided by a previous scheduler operation, the output queue decision made by the current scheduler operation may not be the best decision. In above examples shown inFIG. 4andFIG. 6, the decision buffer device408has only one FIFO buffer410for buffering queue indices of scheduled output queues associated with the same egress port. In a case where an output queue with a queue ID still buffered in the FIFO buffer410is blocked from outputting any packet through the egress port due to certain performance consideration, any of the following queue IDs in the FIFO buffer410cannot be output. As a result, the traffic with higher class may be blocked by lower class traffic; the performance will be significantly degraded if the packet of lower class traffic is a long packet. To solve this issue, the present invention further proposes a class of service (CoS) based FIFO design. More specifically, packets belonging to services with different priorities may be categorized into packet traffics with different traffic classes when forwarded through the egress port. The present invention therefore proposes assigning different decision FIFO buffers to different traffic classes, thus preventing the traffic with lower traffic class from blocking traffic with higher traffic class. Further details are described as below.

Please refer toFIG. 8, which is a diagram illustrating a network switch according to a fourth embodiment of the present invention. The network switch800includes a decision buffer device808and the aforementioned dequeue device104/404, scheduler406and buffer memory device102. In this embodiment, the decision buffer device808includes a ranker812, a plurality of FIFO buffers814_1-814_M corresponding to different traffic classes, and a ranker sorter816. The ranker demux812is arranged to store a queue index of a scheduled output queue decided by each scheduler operation performed by the scheduler406to one of the FIFO buffers814_1-814_M based on a traffic class of the scheduled output queue. Besides, a ranker sorter816may further sort queue indices over the FIFO buffers814_1-814_M based on corresponding priority settings, thereby properly adjusting the output sequence of the queue indices in the decision FIFOs. In this embodiment, the decision buffer device808has multiple FIFO buffers rather than a single FIFO buffer. When a lower-priority output queue with a queue ID still buffered in one FIFO buffer corresponding to a lower traffic class is blocked from outputting any packet through the egress port due to certain performance consideration, a higher-priority output queue with a queue ID still buffered in another FIFO buffer corresponding to a higher traffic class is allowed to be selected for outputting its buffered packet data. In this way, the desired line rate of the egress port can be sustained.