Scheduling methods for combined unicast and multicast queuing
View Patent ↗An improved combined Switching Data Unit (SDU) queuing discipline for unicast and multicast (Protocol Data Unit) PDU forwarding at a switching node is provided. Multicast SDU descriptors are replicated and stored in entries of a First-In/First-Out queue portion of a hybrid output port queue. Unicast SDU descriptors are chained in entries of a linked list queue portion of the hybrid output port queue. Servicing of the hybrid queue uses hybrid queue counters, and inter-departure-counters stored in multicast FIFO queue entries to keep track of the number of unicast SDU linked list entries, to be serviced between the multicast FIFO queue entries. The combined hybrid queue derives storage efficiency benefits from linking unicast PDUs in linked lists and further derives benefits from a simple access to multicast PDU entries.
1. A hybrid queue for an output port of a protocol data unit (PDU) switching node comprising:
a. a first input first output (FIFO) queue configured to store multicast FIFO entries, each multicast FIFO entry further comprising a multicast switching data unit (SDU) descriptor pointer and an inter-departure-counter specifier holding a number of unicast SDUs to be serviced ahead of the multicast SDU entry; each multicast SDU descriptor comprising a diversity field for specifying the number of output ports the multicast PDU is to be conveyed through;
b. a linked list queue defined by a plurality of unicast SDU entries, each unicast SDU entry further comprising a unicast SDU descriptor, each unicast SDU descriptor further comprising a next SDU descriptor pointer;
c. a unicast forwarding request arrival counter for counting unicast PDU forwarding requests received between multicast FIFO entries, the arrival counter being incremented with each unicast PDU forwarding request arrival, the arrival counter being decremented with each serviced unicast SDU entry if the multicast FIFO queue is empty, the value of the arrival counter being further copied to the inter-departure-counter of a subsequently received multicast FIFO entry upon receiving a multicast PDU forwarding request and the value of the arrival counter being reset to zero thereafter;
d. a unicast PDU departure counter for counting unicast PDU departures between multicast PDU departures in servicing the unicast linked list queue if the multicast FIFO queue is not empty; and
e. a sequencer for servicing unicast linked list entries and multicast FIFO queue entries, the sequencer servicing a next multicast FIFO entry if the value of the departure counter equates the value held in an inter-departure-count held in said next multicast FIFO entry and otherwise servicing the next unicast linked list entry pointed to by a head-of-line pointer specifier;
the combined unicast and multicast PDU forwarding request queuing benefiting from bandwidth efficient FIFO queuing of multicast forwarding requests, and memory storage efficient linked list queuing of unicast PDUs.
2. The hybrid queue of claim 1 , wherein each SDU descriptor pointer is chained to a next SDU pointer field.
3. The hybrid queue of claim 1 , further comprising a fan out diversity field configured to store data related to at least one output port.
4. The hybrid queue of claim 1 , wherein memory space for the FIFO queue is reserved from a control shared buffer.
5. The hybrid queue of claim 1 , wherein the sequencer is configured to select between unicast and multicast SDU FIFO entries.
6. The hybrid queue of claim 1 , further comprising a head-of-line (HOL) pointer specifier, the HOL pointer specifier being maintained by the hybrid queue.
7. A system comprising:
means for storing multicast first input first output (FIFO) entries, each multicast FIFO entry further comprising a multicast switching data unit (SDU) descriptor pointer and an inter-departure-counter specifier holding a number of unicast SDUs to be serviced ahead of the multicast SDU entry, each multicast SDU descriptor comprising a diversity field for specifying the number of output ports a multicast protocol data unit (PDU) is to be conveyed through;
means for queuing a linked list, the means for queuing defined by a plurality of unicast SDU entries, each unicast SDU entry further comprising a unicast SDU descriptor, each unicast SDU descriptor further comprising a next SDU descriptor pointer;
means for counting unicast PDU forwarding requests received between multicast FIFO entries, the means for counting unicast PDU forwarding requests being incremented with each unicast PDU forwarding request arrival, the means for counting unicast PDU forwarding requests being decremented with each serviced unicast SDU entry if the multicast FIFO queue is empty, the value of the means for counting unicast PDU forwarding requests being further copied to the inter-departure-counter of a subsequently received multicast FIFO entry upon receiving a multicast PDU forwarding request and the value of the means for counting unicast PDU forwarding requests being reset to zero thereafter;
means for counting unicast PDU departures between multicast PDU departures in servicing the unicast linked list queue if the multicast FIFO queue is not empty; and
means for servicing unicast linked list entries and multicast FIFO queue entries, the sequencer servicing a next multicast FIFO entry if the value of the departure counter equates the value held in an inter-departure-count held in said next multicast FIFO entry and otherwise servicing the next unicast linked list entry pointed to by a head-of-line pointer specifier, the combined unicast and multicast PDU forwarding request queuing benefiting from bandwidth efficient FIFO queuing of multicast forwarding requests, and memory storage efficient linked list queuing of unicast PDUs.
8. The system of claim 7 , further comprising means for chaining the descriptor pointer to a next SDU pointer field.
9. The system of claim 7 , further comprising means for storing data related to at least one output port.
10. The system of claim 7 , further comprising means for reserving memory space for the FIFO queue from a control shared buffer.
11. The system of claim 7 , further comprising means for selecting between unicast and multicast SDU FIFO entries.
12. The system of claim 7 , further comprising means for utilizing a head-of-line (HOL) pointer specifier, the HOL pointer specifier being maintained by the hybrid queue.