Granted Patent B2

US 7,649,882 · App. 10/402,589 · Granted Jan 19, 2010

Abstract

Claims (48)

1. A method of routing packets of one or more multicast sessions between ingress ports and egress ports of a switch, the method comprising the steps of:

(a) queuing i) each arriving packet in a corresponding session queue, and ii) an identifier for each new multicast session to a list-of-sessions queue;

(b) queuing a descriptor associated with one or more packets of each multicast session in the list-of-sessions queue to a plurality of interface descriptor queues, each interface descriptor queue associated with only one corresponding egress port of the switch;

(c) selecting, for each of a plurality of non-empty interface descriptor queues, one descriptor of the non-empty interface descriptor queue;

(d) transmitting, for each of the plurality of non-empty interface descriptor queues, one or more packets associated with the selected descriptor in the non-empty interface descriptor queue to the corresponding egress port, and

(e) guaranteeing a bounded time interval between the arrival of an arriving packet at a corresponding session queue and completion of the transmission to the corresponding egress ports of all of the one or more packets corresponding to the arriving packet, wherein:

the bounded time interval is based on the number of multicast sessions and the fan-out of each of the multicast sessions;

the fan-out is defined as the number of egress ports for which packets of a multicast session are to be replicated; and

the fan-out is less than the total number of egress ports of the switch.

2. The invention of claim 1 , further comprising the steps of:

(f) assigning a reference count equivalent to the fan-out of the corresponding multicast session to each arriving packet; and

(g) adjusting the reference count as the corresponding packet is transmitted to the corresponding egress port.

3. The invention of claim 2 , further comprising the steps of:

(h) repeating steps (c), (d), and (g); and

(i) clearing the packet in the switch based on the adjusted reference count.

4. The invention of claim 3 , wherein step (i) clears the packet when the adjusted reference count is zero.

5. The invention of claim 1 , further comprising the step of repeating steps (a) through (d) as packets arrive at the switch.

6. The invention of claim 1 , wherein, for step (b), each descriptor for each session is queued in the plurality of interface descriptor queues in accordance with a round-robin or weighted round-robin scheduling method.

7. The invention of claim 1 , wherein step (c) selects each descriptor of each interface descriptor queue in accordance with a predefined service method.

8. The invention of claim 1 , wherein the bounded time interval is based on a summation of the fan-out of each corresponding multicast session over all of the multicast sessions.

9. Apparatus for routing packets of one or more multicast sessions between ingress ports and egress ports of a switch, the apparatus comprising:

a packet arrival processor adapted to queue i) each arriving packet in a corresponding session queue, and ii) an identifier for each new multicast session to a list-of-sessions queue;

a packet replication processor adapted to queue a descriptor associated with one or more packets of each multicast session in the list-of-sessions queue to a plurality of interface descriptor queues, each interface descriptor queue associated with only one corresponding egress port of the switch; and

a per-interface transmission processor adapted to:

1) select, for each of a plurality of non-empty interface descriptor queues, one descriptor of the non-empty interface descriptor queue; and

2) transmit, for each of the plurality of non-empty interface descriptor queues, one or more packets associated with the selected descriptor in the non-empty interface descriptor queue to the corresponding egress port;

wherein:

the apparatus is adapted to guarantee a bounded time interval between the arrival of an arriving packet at a corresponding session queue and completion of the transmission to the corresponding egress ports of all of the one or more packets corresponding to the arriving packet;

the bounded time interval is based on the number of multicast sessions and the fan-out of each of the multicast sessions;

the fan-out is defined as the number of egress ports for which packets of a multicast session are to be replicated; and

the fan-out is less than the total number of egress ports of the switch.

10. The invention of claim 9 , wherein:

the packet arrival processor is adapted to assign a reference count equivalent to the fan-out of the corresponding multicast session to each arriving packet; and

the per-interface transmission processor is adapted to adjust the reference count as the corresponding packet is transmitted to the corresponding egress port.

11. The invention of claim 10 , wherein the per-interface transmission processor is adapted to clear the packet in the switch based on the adjusted reference count.

12. The invention of claim 9 , wherein each descriptor for each session is queued in the plurality of interface descriptor queues in accordance with a round-robin or weighted round-robin scheduling method.

13. The invention of claim 9 , wherein the bounded time interval is based on a summation of the fan-out of each corresponding multicast session over all of the multicast sessions.

14. A computer-readable storage medium having stored thereon a plurality of computer-executable instructions, the plurality of instructions including instructions which, when executed by a computer, cause the processor to implement a method for routing packets of one or more multicast sessions between ingress ports and egress ports of a switch, the method comprising the steps of:

(a) queuing i) each arriving packet in a corresponding session queue, and ii) an identifier for each new multicast session to a list-of-sessions queue;

(b) queuing a descriptor associated with one or more packets of each multicast session in the list-of-sessions queue to a plurality of interface descriptor queues, each interface descriptor queue associated with only one corresponding egress port of the switch;

(c) selecting, for each of a plurality of non-empty interface descriptor queues, one descriptor of the non-empty interface descriptor queue;

(d) transmitting, for each of the plurality of non-empty interface descriptor queues, one or more packets associated with the selected descriptor in the non-empty interface descriptor queue to the corresponding egress port; and

(e) guaranteeing a bounded time interval between the arrival of an arriving packet at a corresponding session queue and completion of the transmission to the corresponding egress ports of all of the one or more packets corresponding to the arriving packet, wherein:

the bounded time interval is based on the number of multicast sessions and the fan-out of each of the multicast sessions;

the fan-out is defined as the number of egress ports for which packets of a multicast session are to be replicated; and

the fan-out is less than the total number of egress ports of the switch.

15. The invention of claim 14 , wherein, for step (b), each descriptor for each session is queued in the plurality of interface descriptor queues in accordance with a round-robin or weighted round-robin scheduling method.

16. The invention of claim 14 , wherein the bounded time interval is based on a summation of the fan-out of each corresponding multicast session over all of the multicast sessions.

Assignments (10)