Dynamically delisting and relisting multicast destinations in a network switching node

• US 6,625,121 B1
• Filed: 04/28/1999
• Issued: 09/23/2003
• Est. Priority Date: 04/28/1999
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Samrao, Gurmohan, Lau, Onchuen, Chui, Gene, Kipnis, Gary
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): Pezzlo, John
• Application Number:
  US09/301,519
• Time in Patent Office: 1,609 Days
• Field of Search: 370/230, 370/389, 370/390, 370/239, 370/232, 370/429, 370/428, 370/414, 370/397, 370/418, 370/412, 370/254, 370/392, 370/395.1, 370/398, 370/395.72, 370/395.71, 709/234, 710/57
• US Class Current: 370/230
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 2012/5681 Buffer or queue management
• CPC Class Codes: H04L 2012/5682 Threshold; Watermark
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• 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 49/203 ATM switching fabrics with multicast or broadcast capabilities
• CPC Class Codes: H04L 49/90 Buffering arrangements

Abstract

An apparatus and method for reducing congestion in a network switching node. A congestion mask that indicates which of a plurality of destination ports in a network switching node are congested is generated and combined with a destination port field included in a packet in a multicast queue of the switching node to mask destination port designations in the destination port field that are indicated by the congestion mask to be congested if a drop eligibility field within the packet indicates that destination port designations are permitted to be masked. The packet is dequeued from the multicast queue to be forwarded to destination ports in the network switching node indicated by destination port designations in the destination port field not masked by the combination of the congestion mask with the destination port field.

Claims

1. A method of reducing congestion in a network switching node, the method comprising:

masking destination port designations that correspond to congested destinations in the switching node from a destination port field included in a first packet in a multicast queue of the switching node if a drop eligibility value within the packet indicates that destination port designations may be masked; and

dequeuing the first packet from the multicast queue to be forwarded to destination ports indicated by unmasked destination port designations in the destination port field, the dequeuing permitting advance of other packets in the multicast queue.

2. The method of claim 1 wherein masking destination port designations from the destination port field included in the first packet comprises:

generating a congestion mask that indicates which of a plurality of destination ports in the network switching node are congested; and

combining the congestion mask with the destination port designations in the destination port field to suppress destination port designations for the destination ports that are congested.

3. The method of claim 2 wherein generating the congestion mask comprises asserting a respective speedup signal for each of a plurality of virtual output queues in the switching node that is unable to receive incoming cells at an assigned rate, each speedup signal forming a portion of the congestion mask.

4. The method of claim 2 wherein generating the congestion mask comprises generating the congestion mask based on congestion information received from the destination ports.

5. The method of claim 1 further comprising:

issuing a request to a switching fabric included in the switching node to forward the first packet to the destination ports indicated by the unmasked destination port designations in the destination port field;

receiving a grant indication from the switching fabric granting the request to forward the first packet to the destination ports indicated by the unmasked destination port designations; and

wherein said dequeuing the first packet from the multicast queue is performed in response to the grant indication.

6. The method of claim 5 wherein masking destination port designations comprises generating a dynamic destination port mask by combining the destination port designations with a congestion mask that indicates which of a plurality of destination ports are congested, and wherein issuing a request to the switching fabric comprises transmitting information representative of the dynamic destination port mask to the switching fabric.

7. The method of claim 1 wherein masking destination port designations comprises generating a dynamic destination port mask by combining the destination port designations with a congestion mask that indicates which of a plurality of destination ports are congested, the destination port designations in the destination port field in the first packet remaining unchanged.

8. The method of claim 1 further comprising unmasking a previously masked destination port designation from a destination port field included in a second packet in the multicast queue in response to determining that a previously congested destination port that corresponds to the previously masked destination port designation has become uncongested.

9. The method of claim 1 wherein the first packet is a fixed length cell.

10. The method of claim 1 wherein the network switching node is an asynchronous transfer mode (ATM) switch.

11. The method of claim 1 further comprising determining whether the drop eligibility value exceeds a predetermined threshold, the drop eligibility value indicating that destination port designations may be masked if the drop eligibility value exceeds the predetermined threshold.

12. A method of reducing congestion in a network switching node, the method comprising:

generating a congestion mask that indicates which of a plurality of destination ports in the switching node are congested;

combining the congestion mask with a destination port field included in a packet in a multicast queue of the switching node to mask destination port designations in the destination port field that are indicated by the congestion mask to be congested if a drop eligibility field within the packet indicates that destination port designations are permitted to be masked; and

dequeuing the packet from the multicast queue to be forwarded to destination ports in the network switching node indicated by destination port designations in the destination port field not masked by said combining the congestion mask with the destination port field.

13. The method of claim 12 wherein combining the congestion mask with the destination port field comprises generating a first dynamic destination port mask in which the destination port designations in the destination port field that are indicated by the congestion mask to be congested are masked if the drop eligibility field indicates that destination port designations are permitted to be masked, the destination port field being undisturbed by the combining with the congestion mask.

14. The method of claim 13 further comprising generating a second dynamic destination port mask based on a combination of an updated congestion mask with the destination port field, the updated congestion mask indicating that at least one previously congested destination port has become uncongested so that a corresponding destination port designation that was masked in the first dynamic destination port mask is unmasked in the second dynamic destination port mask.

15. The method of claim 12 wherein the packet is a fixed length cell.

16. The method of claim 12 wherein the network switching node is an asynchronous transfer mode (ATM) switch.

17. An apparatus comprising:

a multicast queue to store a data packet destined for multiple network destinations; and

port mask generation circuitry to combine congestion information with a destination port field included in the data packet and a drop eligibility field included in the data packet to generate a dynamic destination port mask that indicates destination ports in a network switching node to which the data packet is to be forwarded, at least one destination port designation in the destination port field being masked in the dynamic destination port mask if the congestion information indicates that a corresponding one of the destination ports is congested and if the drop eligibility field contains a value that exceeds a predetermined threshold.

18. The apparatus of claim 17 wherein the apparatus is a line card for use in the network switching node, the line card further comprising an interface to receive a network transmission line.

19. The apparatus of claim 17 further comprising a plurality of virtual output queues to store data packets destined for respective ones of the destination ports, and wherein the congestion information is generated based on which of the plurality of virtual output queues is unable to receive incoming data packets at an assigned rate.

20. The apparatus of claim 17 further comprising an interface to couple the apparatus to a switching fabric in the network switching node, and wherein the congestion information is received from the switching fabric via the interface.

21. The apparatus of claim 17 wherein the data packet is a fixed-length cell.

22. A network switching node comprising:

a switching fabric; and

a plurality of line cards coupled to the switching fabric, each of the line cards constituting at least one destination port in the network switching node, each of the line cards including

a multicast queue to store a data packet destined for multiple network destinations, and

port mask generation circuitry to combine congestion information with a destination port field included in the data packet and a drop eligibility field included in the data packet to generate a dynamic destination port mask that indicates to which of the destination ports in the network switching node the data packet is to be forwarded, at least one destination port designation in the destination port field being masked in the dynamic destination port mask if the congestion information indicates that a corresponding one of the destination ports is congested and if the drop eligibility field contains a value that exceeds a predetermined threshold.

23. The network switching node of claim 22 wherein the network switching node is an asynchronous transfer mode (ATM) switch.

24. An apparatus comprising:

a multicast queue to store a data packet destined for multiple network destinations; and

port mask generation circuitry to combine congestion information with a destination port field associated with the data packet and a drop eligibility field associated with the data packet to generate a dynamic destination port mask that indicates destination ports in a network switching node to which the data packet is to be forwarded, wherein a destination port designation in the destination port field is masked in the dynamic destination port mask if the congestion information indicates that a corresponding one of the destination ports is congested and if the drop eligibility field contains a value that indicates that the packet is eligible to be dropped.

25. The apparatus of claim 24 wherein the apparatus is a line card for use in the network switching node, the line card further comprising an interface to receive a network transmission line.

26. The apparatus of claim 24 further comprising a plurality of virtual output queues to store data packets destined for respective ones of the destination ports, and wherein the congestion information is generated based on which of the plurality of virtual output queues is unable to receive incoming data packets at an assigned rate.

27. The apparatus of claim 24 further comprising an interface to couple the apparatus to a switching fabric in the network switching node, and wherein the congestion information is received from the switching fabric via the interface.

28. The apparatus of claim 24 wherein the data packet is a fixed-length cell.

29. An apparatus for reducing congestion in a network switching node, the apparatus comprising:

means for masking destination port designations that correspond to congested destinations in the switching node from a destination port field associated with a first packet in a multicast queue of the switching node if a drop eligibility value within the packet indicates that destination port designations may be masked; and

means for dequeuing the first packet from the multicast queue to be forwarded to destination ports indicated by unmasked destination port designations in the destination port field, the dequeuing permitting advance of other packets in the multicast queue.

30. The apparatus of claim 29 wherein the means for masking destination port designations from the destination port field associated with a first packet further comprises:

means for generating a congestion mask that indicates which of a plurality of destination ports in the network switching node are congested; and

means for combining the congestion mask with the destination port designations in the destination port field to suppress destination port designations for the destination ports that are congested.

31. The apparatus of claim 30 wherein the means for generating the congestion mask further comprises means for asserting a respective speedup signal for each of a plurality of virtual output queues in the switching node that is unable to receive incoming cells at an assigned rate, each speedup signal forming a portion of the congestion mask.

32. The apparatus of claim 30 wherein the means for generating the congestion mask further comprises means for generating the congestion mask based on congestion information received from the destination ports.

33. The apparatus of claim 29 further comprising:

means for issuing a request to a switching fabric included in the switching node to forward the first packet to the destination ports indicated by the unmasked destination port designations in the destination port field; and

means for receiving a grant indication from the switching fabric granting the request to forward the first packet to the destination ports indicated by the unmasked destination port designations, wherein said dequeuing the first packet from the multicast queue is performed in response to the grant indication.

34. The apparatus of claim 33 wherein the means for masking destination port designations further comprises means for generating a dynamic destination port mask by combining the destination port designations with a congestion mask that indicates which of a plurality of destination ports are congested, and wherein the means for issuing a request to the switching fabric further comprises means for transmitting information representative of the dynamic destination port mask to the switching fabric.

35. The apparatus of claim 29 wherein the means for masking destination port designations further comprises means for generating a dynamic destination port mask by combining the destination port designations with a congestion mask that indicates which of a plurality of destination ports are congested, the destination port designations in the destination port field associated with the first packet remaining unchanged.

36. The apparatus of claim 29 further comprising means for unmasking a previously masked destination port designation from a destination port field associated with a second packet in the multicast queue in response to determining that a previously congested destination port that corresponds to the previously masked destination port designation has become uncongested.

37. The apparatus of claim 29 wherein the first packet is a fixed length cell.

38. The apparatus of claim 29 wherein the network switching node is an asynchronous transfer mode (ATM) switch.

39. The apparatus of claim 29 further comprising means for determining whether the drop eligibility value indicates that the packet is eligible to be dropped, the drop eligibility value indicating that destination port designations may be masked if the drop eligibility value indicates that the packet is eligible to be dropped.