MULTICAST REPLICATION SKIP

• US 20140064081A1
• Filed: 08/31/2012
• Published: 03/06/2014
• Est. Priority Date: 08/31/2012
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Morandin, Guglielmo Marco
• Granted Patent: US 9,059,915 B2
• Time in Patent Office: Days
• US Class Current: 370/235
• CPC Class Codes: H04L 43/0882 Utilisation of link capacity
• CPC Class Codes: H04L 47/12 Avoiding congestion; Recovering from congestion
• CPC Class Codes: H04L 47/15 in relation to multipoint traffic arrangements for broadcast or multicast in data networks H04L12/18
• CPC Class Codes: H04L 47/30 in combination with information about buffer occupancy at either end or at transit nodes
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames

Abstract

In one implementation, the volumes of the queues in a network device are monitored to identify ports that are congested or near congestion. In another implementation, an auxiliary queue or counter is used to measure the long term congestion or predict future congestion. The auxiliary queue includes a counter that tracks the occupancy of the queue through a service rate that is less than the service rate of the queue. The service rate of the queue may be the data rate at which data leaves the queue. The service rate of the counter or auxiliary queue may be the speed at which the value of the counter changes. Forced packet dropping may be applied to packets destined to queues associated with a counter that exceeds a threshold.

Claims

1. A method comprising:

receiving a flow of incoming packets;

replicating the flow of incoming packets for a plurality of egress ports;

receiving the replicated packets at a real queue of one of the plurality of egress ports; and

counting the replicated packets in a virtual queue as an indicator of congestion in the real queue.

2. The method of claim 1, further comprising:

comparing a quantity in the virtual queue to a predetermined threshold; and

dropping one or more replicated packets destined for the one of the plurality of egress ports in response to the virtual queue exceeding the predetermined threshold.

3. The method of claim 1, wherein the virtual queue measures a number of the replicated packets sent to the one of the plurality of egress ports.

4. The method of claim 1, wherein the virtual queue measures an amount of data of in the replicated packets sent to the one of the plurality of egress ports.

5. The method of claim 1, wherein the virtual queue lags the real queue in time.

6. The method of claim 1, wherein a first service rate associated with the virtual queue is less than a second service rate associated with the real queue.

7. The method of claim 1, wherein a first service rate (R) associated with the real queue and a second service rate (X) is associated with the virtual queue according to X=R*(1−

ε

), wherein ε

is a value between 0 and 1.

8. The method of claim 7, where E is ¼

, ⅛

, Pi/4, or 1/32.

9. The method of claim 1, wherein when X is less than R over time, the real queue is empty and a quantity value of the virtual queue is zero, when X is greater than R over time the real queue increases at a first rate and the virtual queue increases at a second rate.

10. The method of claim 9, wherein the second rate is greater than the first rate.

11. The method of claim 1, wherein the virtual queue tracks the occupancy of the real queue.

12. A network device comprising:

an input communication interface configured to receive a sequence of data packets;

a controller configured to direct the sequence of data packets to a queue having a first rate and accumulate, at a second rate, a count value associated with the queue according to an amount of data in the sequence of data packets; and

an output communication interface that receives the sequence of data packets until the count value exceeds a predetermined threshold.

13. The network device of claim 12, wherein the second rate is less than the first rate.

14. The network device of claim 12, wherein the first rate describe a rate that data exits the queue.

15. The network device of claim 12, wherein the controller is configured to replicate data packets destined for the output communication interface when the count value is less than the predetermined threshold and configured to drop data packets destined for the output communication interface when the count value is greater than the predetermined threshold.

16. The network device of claim 12, further comprising:

a shadow queue configured to store the count value and lag the queue based on a difference between the second rate and the first rate.

17. The network device of claim 12, wherein the second rate (X) is associated with the first rate (R) according to X=R*(1−

ε

), wherein ε

is a value between 0 and 1.

18. A non-transitory computer readable medium containing instructions that when executed are configured to:

receive a flow of incoming packets;

replicate the flow of incoming packet as replicated packets;

send the replicated packets to a plurality of egress ports;

receive the replicated packets at a real queue of one of the plurality of egress ports; and

compare data indicative of an occupancy of the real queue to a predetermined threshold.

19. The non-transitory computer readable medium of claim 18, the instructions further configured to:

count the replicated packets in a virtual queue as the data indicative of the occupancy of the real queue.

20. The non-transitory computer readable medium of claim 18, wherein the data indicative of the occupancy of the real queue is a real time volume of the real queue.