Granted Patent B2

US 7,609,693 · App. 10/443,505 · Granted Oct 27, 2009

Assignee: Alcatel-Lucent USA Inc.

Abstract

Claims (77)

1. A method of queuing multicast packets for transmission to multiple destinations, comprising:

associating a multicast pointer with a multicast packet;

enqueuing copies of the multicast pointer in multiple destination queues, wherein each copy of the multicast pointer is associated with a destination;

keeping track of valid destinations to which the multicast packet is directed, but to which a copy of the multicast packet has not been sent; and

recycling the multicast pointer after a copy of the multicast packet is sent to each of the valid destinations.

2. The method of claim 1 , further comprising:

receiving a first cell of said multicast packet, wherein said associating specifically associates said multicast pointer with the first cell of said multicast packet.

3. The method of claim 2 , further comprising:

determining a destination mask using information associated with said multicast packet; and

associating the destination mask with said multicast pointer.

4. The method of claim 1 , further comprising:

receiving said multicast packet;

storing said multicast packet in packet memory;

sending a copy of said multicast packet to one of said valid destinations; and

updating information associated with said multicast pointer.

5. The method of claim 4 , wherein said multicast pointer is a start-of-packet (SOP) pointer, further comprising:

associating other pointers with said multicast packet such that each cell of the packet is specifically associated with a pointer, wherein the SOP cell of the packet is specifically associated with a SOP pointer;

enqueuing said SOP pointer at a plurality of queue locations; and

enqueuing an end-of-packet (LOP) pointer at fewer than said plurality of queue locations.

6. The method of claim 5 , further comprising:

dequeuing said multicast packet; and

updating information associated with said SOP pointer.

7. The method of claim 6 , further comprising:

dequeuing a next packet at a queue location identified by an auxiliary pointer from said SOP pointer.

8. The method of claim 4 , further comprising:

performing random early drop (RED) on said multicast packet; and

dropping one or more valid destinations in accordance with said performing.

9. The method of claim 1 , further comprising:

associating a unicast pointer with a unicast packet;

storing the unicast packet in packet memory;

sending the unicast packet from packet memory; and

recycling the unicast pointer.

10. A method of queuing multicast packets for transmission to multiple destinations, comprising:

maintaining a first queue associated with a first destination;

maintaining a second queue associated with a second destination;

enqueuing a multicast staff-of-packet (SOP) pointer associated with a packet on the first queue;

enqueuing the multicast SOP pointer on the second queue; and

recycling a multicast pointer after a copy of a multicast packet is sent to each destination for which the multicast packet has been enqueued.

11. The method of claim 10 , further comprising:

traversing said first queue through said multicast SOP pointer to an end-of-packet (LOP) pointer associated with said packet.

12. The method of claim 11 , further comprising:

continuing to traverse said first queue from said LOP pointer.

13. The method of claim 11 , further comprising:

returning to said multicast SOP pointer; and

continuing to traverse said first queue through an auxiliary pointer associated with said multicast SOP pointer and said first queue.

14. The method of claim 11 , further comprising:

traversing from said second queue through said multicast SOP pointer to said LOP pointer.

15. The method of claim 10 , further comprising:

determining that said packet has been sent to each valid destination to which the packet is directed; and

recycling said multicast SOP pointer.

16. A system for queuing multicast packets for transmission to multiple destinations, comprising:

a receive module configured to:

receive cells, including a first cell and a second cell;

determine that the first cell is a multicast start-of-packet (SOP) cell;

establish that the second cell is a unicast SOP cell;

associate a first type of pointer with the first cell in accordance with said determination; and

associate a second type of pointer with the second cell in accordance with said establishing;

a plurality of packet queues configured to:

enqueue the pointer associated with the first cell in a subplurality of the plurality of packet queues; and

enqueue the pointer associated with the second cell in one of the plurality of packet queues;

wherein the first cell is associated with a first packet and the second cell is associated with a second packet;

a transmit module configured to transmit the packets;

a multicast packet cleanup engine configured to recycle a multicast pointer after a copy of a multicast packet is sent to each destination for which the multicast packet has been enqueued.

17. The system of claim 16 , wherein the receive module is further configured to:

determine whether a received cell is not a multicast SOP cell; and

associate the second type of pointer with the received cell.

18. The system of claim 16 , further comprising:

a free pointers buffer with a first list of pointers of said first type and a second list of pointers of said second type, wherein each pointer of said first type includes a main pointer and an auxiliary pointer; and

a packet constructor configured to reassemble packets from the received cells.

19. The system of claim 16 , further comprising:

a destination mask lookup table, wherein each destination mask identifies a set of destinations for said reassembled packets,

wherein said receive module is further configured to:

look up a destination mask using data associated with said first cell; and

associate the destination mask with said first cell.

20. The system of claim 19 , further comprising:

packet memory configured to store the received cells,

wherein the transmit module is further configured to release memory in which a packet, including said first cell, is stored in the packet memory when said packet is transmitted to each valid destination of said set of locations.

Assignments (10)

Continuity (2)