Memory load balancing for single stream multicast

• US 7,859,999 B1
• Filed: 09/20/2007
• Issued: 12/28/2010
• Est. Priority Date: 07/31/2002
• Status: Expired due to Fees

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Lim, Raymond M., Basu, Debashis, Godbole, Avanindra, Libby, Jeffrey G.
• Primary Examiner(s): HSU, ALPUS
• Application Number:
  US11/858,323
• Time in Patent Office: 1,195 Days
• Field of Search: 370/230, 370/235, 370/412, 370/474
• US Class Current: 370/230
• CPC Class Codes: H04L 12/1886 with traffic restrictions for efficiency improvement, e.g. involving subnets or subdomains
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04L 47/36 by determining packet size, e.g. maximum transfer unit [MTU]
• CPC Class Codes: H04L 47/43 Assembling or disassembling of packets, e.g. segmentation and reassembly [SAR]

Abstract

A system for multicasting a packet of data to a single data stream is provided. The system may determine a size of the packet and may send a single copy of the packet if the size of the packet exceeds a threshold value. A number of copies of the packet yet to be multicast may be ascertained if the size of the packet of data does not exceed the threshold value. Copies of the packet may be transmitted based on the number of copies of the packet yet to be multicast.

Claims

1. A method comprising:

dequeuing buffered packet information having an associated multicast count of greater than one;

determining whether stored packet data corresponding to the buffered packet information exceeds a first threshold;

when the stored packet data corresponding to the buffered packet information exceeds the first threshold;

decrementing the multicast count by one;

copying the buffered packet information and the stored packet data, and

forming one packet from the copied packet information and the copied packet data; and

when the stored packet data corresponding to the buffered packet information does not exceed the first threshold and the multicast count does not exceed a second threshold, where the multicast count equals a number Y and Y is an integer greater than one;

forming, from the buffered packet information and the stored packet data, Y number of packets.

2. The method of claim 1, when decrementing the multicast count by one reduces the multicast count to one, the method further comprising:

subsequently dequeuing the buffered packet information; and

forming one packet from the buffered packet information and the stored packet data.

3. The method of claim 2, further comprising:

dequeuing other buffered packet information, where subsequently dequeuing the buffered packet information is performed after dequeuing the other buffered packet information.

4. The method of claim 1, further comprising:

when the stored packet data corresponding to the buffered packet information does not exceed the first threshold and the multicast count exceeds the second threshold;

decrementing the multicast count by a positive integer, X,

copying the buffered packet information and the stored packet data,

setting, to X, a second multicast count associated with the copied packet information, and

forming, from the copied packet information and the copied packet data, X number of packets.

5. The method of claim 4, when decrementing the multicast count by X reduces the multicast count to one, the method further comprising:

subsequently dequeuing the buffered packet information; and

forming one packet from the buffered packet information and the stored packet data.

6. The method of claim 5, further comprising:

dequeuing other buffered packet information, where subsequently dequeuing the buffered packet information is performed after dequeuing the other buffered packet information.

7. The method of claim 1, where the threshold relates to a size of the stored packet data.

8. The method of claim 1, when the stored packet data corresponding to the buffered packet information exceeds the first threshold, the method further comprising:

setting, to one, a multicast count associated with the copied packet information.

9. A method comprising:

selecting, from a plurality of queues buffering packet information that corresponds to packet data stored in a first memory, a first one of the queues;

determining, based on the packet information buffered in the first queue, whether packet information at a head of the first queue indicates multicasting;

storing, in a second memory, when the packet information does not indicate multicasting, the packet information from the head of the first queue and the corresponding packet data from the first memory;

determining, when the packet information indicates multicasting, whether the corresponding packet data stored in the first memory exceeds a packet size threshold; and

dequeuing the packet information at the head of the first queue when the corresponding packet data stored in the first memory exceeds the packet size threshold.

10. The method of claim 9, further comprising:

determining, when the corresponding packet data stored in the first memory does not exceed the packet size threshold, whether a multicasting count associated with the indicated multicasting exceeds a multicast count threshold.

11. The method of claim 10, further comprising:

storing, in the second memory, the packet information from the head of the first queue and the corresponding packet data from the first memory when the multicasting count does not exceed the multicast count threshold.

12. The method of claim 11, where the packet information and the corresponding packet data stored in the second memory have an associated multicast count of Y, wherein Y is a positive integer, the method further comprising:

sequentially forming, at a packet assembler, Y number of packets from the head packet information and the corresponding packet data stored in the second memory.

13. The method of claim 12, further comprising:

setting the packet size threshold based on buffer space available in the packet assembler.

14. The method of claim 12, further comprising:

creating, at the packet assembler, different headers for one or more of the Y packets.

15. The method of claim 10, further comprising:

dequeuing the packet information at the head of the first queue when the multicasting count exceeds the multicast count threshold.

16. The method of claim 15, where the dequeuing comprises:

decrementing, by X, a multicast count associated with the packet information at the head of the first queue, where X is a positive integer and does not exceed the multicast count threshold,

copying the packet information and the stored packet data,

setting, to X, a multicast count associated with the copied packet information, and

storing the copied packet information and the copied packet data in the second memory.

17. The method of claim 16, further comprising:

sequentially forming, at a packet assembler, X number of packets from head packet information and the corresponding packet data stored in the second memory.

18. The method of claim 17, further comprising:

retaining the packet information at the head of the first queue after the dequeuing the packet information at the head of the first queue;

selecting a second one of the queues on which to perform dequeue operations; and

subsequently selecting the first queue for subsequently dequeuing the packet information retained at the head of the first queue after the dequeue operations are performed on the second queue.

19. The method of claim 17, further comprising:

setting the multicast count threshold based on an available number of memory banks in the packet assembler.

20. The method of claim 17, further comprising:

creating, at the packet assembler, different headers for one or more of the X number of packets.

21. The method of claim 17, further comprising:

decrementing the multicast count associated with the copied packet information each time one of the X number of packets is formed.

22. A network device comprising:

a first memory to store packet data;

an arbitrator to select a first queue from among a plurality of queues buffering packet information that corresponds to the stored packet data;

a dequeue engine to determine, based on the packet information buffered in the first queue, whether packet information at a head of the first queue indicates multicasting; and

a second memory to store, when the packet information does not indicate multicasting, the packet information from the head of the first queue and the corresponding packet data from the first memory,

the dequeue engine being further configured to;

determine, when the packet information indicates multicasting, whether the corresponding packet data stored in the first memory exceeds a packet size threshold, and

dequeue the packet information at the head of the first queue when the corresponding packet data stored in the first memory exceeds the packet size threshold.