Output queuing method for forwarding packets in sequence
AssigneeVIA Technologies, Inc.
InventorsJen-Kai Chen, Yu-Ju Lin, Jiann-Hwa Liou
Life of this patent
Estimating the term…
Abstract
A output queuing method for forwarding the packets sequentially in a switching network. Each port is related to a port output queue and a global output queue is shared by all port output queues. A FIFO (First In First Out) block is allocated into each port output queue and the global output queue. The FIFO block contains a number of FIFO nodes. Based on the type and destination ports of the received packet, the fields of the related FIFO node in the port output queue and the global output queue are set. The packets are sent out or skipped based on the related fields.
Claims23
An output queuing method for forwarding packets in a switching network, the switching network containing a plurality of ports, each port corresponding to a port output queue, a global output queue shared by all port output queues, a plurality of first in first out, FIFO, blocks allocated to all of the port output queues and to the global output queue, each of the FIFO blocks comprising Nb FIFO nodes and a pointer, Nb being a natural number, each FIFO node comprising a first field and a second field, the output queuing method comprising:
- receiving a packet and identifying the type and the destination port of the received packet so as to enqueue a FIFO node relating to the received packet into one of the global output queue and the port output queues;
- if the received packet is a unicast packet, setting the first and second fields of a unicast FIFO node in the port output queue of the destination port, wherein the unicast FIFO node is regarded as the FIFO node relating to the received packet enqueued into the port output queue of the destination port;
- if the received packet is a multicast packet,
- setting the second field of a multicast FIFO node in the global output queue according to the destination ports of the multicast packet, wherein the multicast FIFO node is regarded as the FIFO node relating to the received packet enqueued into the global output queue;
- and
- setting the first field and the second field of a last unicast FIFO node in each port output queue so as to indicate how many multicast packets following a unicast packet related to the last unicast FIFO node in each port output queue are to be skipped and dequeued, respectively;
- when the received packet is the unicast packet and is being processed,
- reading the first field and the second field in the unicast FIFO node corresponding to the unicast packet and sending out the unicast packet;
- and
- sending out or skipping at least a multicast packet following the received packet according to the first field and the second field of the unicast FIFO node and the second field of the multicast FIFO node related to the multicast packet following the received packet.
An output queuing method for forwarding packets in a switch network, the switch network containing a plurality of ports, each port corresponding to a port output queue, a global output queue shared by all port output queues, the packets being of the type of unicast or multicast, the output queuing method comprising:
- detecting the type of a receiving packet;
- if the type of the receiving packet is unicast, allocating the receiving packet into the port output queue by enqueuing a unicast node corresponding to the receiving packet into the port output queue, wherein the unicast node comprises a multicast count field and the multicast count field is initialized for counting how many multicast nodes corresponding to multicast packets that follow the receiving packet are enqueued into the global output queue;
- if the type of the receiving packet is multicast, allocating the receiving packet into the global output queue by enqueuing a multicast node corresponding to the receiving packet into the global output queue, and by setting, for each of the port output queues, a multicast count field of a unicast node which is last enqueued to indicate how many multicast nodes corresponding to multicast packets that follow a corresponding unicast packet of the last enqueued unicast node have been enqueued into the global output queue;
- and
- when the receiving packet is unicast and is to be transmitted:
- dequeuing the unicast node corresponding to the receiving packet from the port output queue;
- sending out the receiving packet;
- and
- determining whether to perform multicast packet forwarding from the global output queue according to the unicast node corresponding to the receiving packet.
An output queuing method for forwarding packets in a switching network having a plurality of ports, the method comprising:
- providing a plurality of port output queues, each port output queue corresponding to one of the ports for a plurality of unicast nodes to be enqueued in order to forward corresponding unicast packets, wherein each unicast node comprises a multicast count field and the corresponding unicast packet is destined to one of the ports;
- providing a global output queue shared by all of the port output queues for a plurality of multicast nodes to be enqueued in order to forward corresponding multicast packets, wherein each multicast packet is destined to corresponding ones of the ports, and the multicast node corresponding to the multicast packet comprises an output port field indicative of the corresponding ones of the ports;
- in response to an incoming packet,
- if the incoming packet is unicast, enqueuing a unicast node corresponding to the incoming packet into a corresponding one of the port output queues, wherein the multicast count field of the unicast node corresponding to the incoming packet is initialized for counting how many multicast nodes corresponding to multicast packets that follow the incoming packet are enqueued into the global output queue;
- and
- if the incoming packet is multicast,
- enqueuing a multicast node corresponding to the incoming packet into the global output queue;
- and
- for each of the port output queues, setting the multicast count field of a unicast node which is last enqueued to indicate how many multicast nodes corresponding to multicast packets that follow a corresponding unicast packet of the last enqueued unicast node have been enqueued into the global output queue;
- for each of the port output queues with a unicast node that is first enqueued,
- dequeuing the first enqueued unicast node from the port output queue;
- sending out a corresponding unicast packet of the first enqueued unicast node;
- and
- determining whether to perform multicast packet forwarding from the global output queue according to the first enqueued unicast node.
An apparatus for packet forwarding in a switching network having a plurality of ports, the apparatus comprising:
- a queue control module for providing a plurality of port output queues for unicast packet forwarding in the corresponding ports, and providing a global output queue shared by all of the port output queues for multicast packet forwarding;
- an input control module, in response to an incoming packet, for buffering the incoming packet and enqueuing a node corresponding to the incoming packet into one of the global output queue and the port output queues, wherein when the incoming packet is unicast, the node comprises a multicast count field and is enqueued into a corresponding one of the port output queues which corresponds to a destination port of the incoming packet, and when the incoming packet is multicast, the node comprises a port mask field indicative of destination ports of the incoming packet and is enqueued into the global output queue;
- and
- an output control module, for each of the port output queues, for dequeuing a node that is first enqueued, sending out a unicast packet corresponding to the first enqueued node, and determining whether to perform multicast packet forwarding from the global output queue according to the first enqueued node;
- wherein when the node corresponding to the incoming packet is enqueued into is the corresponding one of the port output queues, the queue control module counts how many nodes corresponding to multicast packets that follow the incoming packet are enqueued into the global output queue;
- wherein when the node corresponding to the incoming packet is enqueued into the global output queue, the queue control module, for each port output queue, sets the multicast count field of a node that is last enqueued into the port output queue to a value indicating how many nodes corresponding to multicast packets that follow the last enqueued node are enqueued into the global output queue.
Dependencies are inferred from the claim text.