Multicast replication skip

• US 9,059,915 B2
• Filed: 08/31/2012
• Issued: 06/16/2015
• 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
• Primary Examiner(s): Nawaz, Asad
• Assistant Examiner(s): PATEL, PARTHKUMAR
• Application Number:
  US13/601,373
• Publication Number:
  US 20140064081A1
• Time in Patent Office: 1,019 Days
• Field of Search: 370/235, 370/230
• US Class Current: 1/1
• 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, 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 and (1−

ε

) is a constant ratio, comparing a count value for the virtual queue to a threshold; and

dropping packets at the real queue when the count value for the virtual queue exceeds a threshold.

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 a count in the virtual queue lags a volume of the real queue in time based on a difference between the first service rate and the second service rate.

6. The method of claim 1, where ¼

, ⅛

, Pi/4, or 1/32.

7. 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, and wherein when X is greater than R over time the real queue increases more quickly than the virtual queue.

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

9. The method of claim 1, wherein the indicator of congestion indicates future congestion when the count value is above zero and the real queue is empty.

10. The method of claim 1, wherein the indicator of congestion indicates future congestion when the count value is increasing and the real queue is empty.

11. 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 service rate and accumulate a count value associated with the queue according to an amount of data in the sequence of data packets, wherein the count value is stored in a shadow queue having a second service rate; and

an output communication interface that receives the sequence of data packets until the count value exceeds a predetermined threshold, 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, wherein the second service rate (X) is associated with the first service rate (R) according to X =R*(1−

ε

), wherein ε

is a value between 0 and 1.

12. The network device of claim 11, wherein the first service rate describes a rate that data exits the queue.

13. The network device of claim 11, wherein the shadow queue is configured to store the count value and lag the queue based on a difference between the second service rate and the first service rate.

14. 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, wherein the real queue drains at a first rate;

track an occupancy of the virtual queue that drains at a second rate, 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; and

compare data indicative of the occupancy of the real queue to a predetermined threshold; and

drop packets at the real queue when the occupancy of the virtual queue exceeds the predetermined threshold.

15. the non-transitory computer readable medium of claim 14, the instructions further configured to:

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

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