Method and apparatus for accumulating and distributing data items within a packet switching system

• US 6,735,173 B1
• Filed: 03/07/2000
• Issued: 05/11/2004
• Est. Priority Date: 03/07/2000
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Lenoski, Daniel E., Turner, Jonathan S.
• Primary Examiner(s): Pham, Chi
• Assistant Examiner(s): LY, ANH VU H
• Application Number:
  US09/520,688
• Time in Patent Office: 1,526 Days
• Field of Search: 370/235, 370/230.1, 370/236, 370/236.1, 370/236.2, 370/359, 370/360, 370/361, 370/412, 370/414, 370/419, 370/450, 370/454
• US Class Current: 370/235
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• 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/33 using forward notification
• CPC Class Codes: H04L 47/35 by embedding flow control information in regular packets, e.g. piggybacking

Abstract

Methods and apparatus are disclosed for accumulating and distributing information in a packet switching system. For example, it is desirable in certain packet switching systems to communicate the status of internal queues and other port status information from an individual port to all other ports (or at least those which are communicating with the individual port). The amount of information being sent from the individual port is typically very small, such as on the order of a few bits or bytes. By accumulating the information and then broadcasting the collected flow control information, a vast amount of switch fabric resources (e.g., bandwidth) can be saved. In one implementation, flow control information is sent to a destination (e.g., a “mailbox”) within a packet switching fabric which includes a memory in which flow control information is accumulated. After a period of time or based on the occurrence of some event, the accumulated flow control information is distributed. This same mechanism may be used to distribute most any type of information (e.g., flow control information, signaling information, and data internal or external to a packet switch or packet switching system).

Claims

1. A method comprising:

receiving one or more packets including flow control information;

accumulating said flow control information from said one or more packets in a data structure;

creating a distribution packet including at least a portion of said flow control information accumulated in the data structure; and

distributing the distribution packet to a plurality of destinations.

2. The method of claim 1, wherein said one or more packets are received from a plurality of sources.

3. The method of claim 1, wherein said method is performed by a packet switch, and at least one of said one or more packets is received from a source external to the packet switch.

4. The method of claim 1, wherein said method is performed by a packet switch, and said distributing the distribution packet includes distributing the distribution packet to a plurality of input interfaces of the packet switch.

5. The method of claim 1, wherein said method is performed by a packet switch, and said distributing the distribution packet includes distributing the distribution packet to a plurality of output interfaces of the packet switch.

6. The method of claim 1, wherein the data structure is a hash table or array.

7. The method of claim 1, wherein said distributing the distribution packet includes distributing the distribution packet after a predetermined time interval after distributing a prior distribution packet.

8. The method of claim 1, wherein said distributing the distribution packet includes distributing the distribution packet after a predetermined period of not receiving a new packet including new flow control information.

9. The method of claim 1, wherein said distributing the distribution packet includes distributing the distribution packet when the data structure is fill.

10. The method of claim 1, wherein said distributing the distribution packet includes distributing the distribution packet to all ports of the packet switch.

11. The method of claim 1, wherein said distributing the distribution packet includes distributing the distribution packet after receipt of a packet including an indication to distribute the distribution packet.

12. The method of claim 1, wherein at least a portion of said one or more packets are received from a plurality of line cards, and wherein said flow control information included in the portion of said one or more packets received from the plurality of line cards includes signaling information between the plurality of line cards.

13. The method of claim 12, wherein the signaling information relates to a subrate channel within a signal received at or transmitted by one or more of the plurality of line cards.

14. The method of claim 12, wherein the plurality of destinations includes the plurality of line cards.

15. The method of claim 14, wherein said method is performed by a packet switch, the packet switch including the plurality of line cards.

16. The method of claim 1, wherein said method is performed by a packet switch, the packet switch including at least one switch element;

and wherein one of said at least one switch element includes the data structure.

17. The method of claim 16, wherein said one of said at least one switch element is a routing stage switch element of the packet switch.

18. The method of claim 16, wherein said one of said at least one switch element is a second stage switch element of a three stage switching fabric of the packet switch.

19. A packet switching system comprising:

a plurality of line cards configured to generate and send a plurality of packets including flow control information; and

a switching fabric including;

a switch fabric mechanism configured to receive at least one of the plurality of packets;

a data structure configured to accumulate the flow control information included in said at least one of the plurality of packets;

a packetizer configured to create a plurality of distribution packets; and

a distributor configured to distribute the plurality of distribution packets to at least a subset of the plurality of line cards.

20. The packet switching system of claim 19, further comprising:

one or more additional switching fabrics, at least a subset of the additional switching fabrics each including;

an additional switching fabric mechanism configured to receive at least a portion of the packets;

an additional switching fabric data structure configured to accumulate the flow control information included in said at least a portion of the packets;

an additional switching fabric packetizer configured to create a plurality of fabric distribution packets; and

an additional switching fabric distributor configured to distribute the plurality of fabric distribution packets to at least a second subset of the line cards.

21. The packet switching system of claim 20, wherein each of the plurality of line cards is configured to send the plurality of packets to at least two switching fabrics from the group including the switching fabric and the additional switching fabrics.

22. A packet switch, including:

a plurality of first switch elements;

a plurality of second switch elements; and

an interface;

wherein each of the plurality of first switch elements is configured to received a first set of flow control information, to accumulate the first set of flow control information to generate an accumulated first set of flow control information, and to distribute the accumulated first set of flow control information to each of the plurality of second switch elements;

said each of the plurality of second switch elements is configured to receive the accumulated first set of flow control information from said each of the plurality of first switch elements, to accumulate said received plurality of accumulated first sets of flow control information to generate an accumulated second set of flow control information, and to distribute the accumulated second set of flow control information to the interface; and

the interface is configured to receive the accumulated second set of flow control information from said each of the plurality of second switch elements, and to accumulate said received plurality of accumulated second sets of flow control information to generate an accumulated interface set of flow control information.

23. The packet switch of claim 22, wherein the interface is configured to generate one or more flow control messages based on the accumulated interface set of flow control information.

24. A packet switch, comprising:

means for receiving flow control information;

means for accumulating said flow control information in a data structure;

means for creating a distribution packet including at least a portion of said flow control information accumulated in the data structure; and

means for distributing the distribution packet to a plurality of destinations.

25. The packet switch of claim 24, wherein the packet switch includes a plurality of line cards, and wherein said flow control information is received from the plurality of line cards.

26. The packet switch of claim 25, wherein the plurality of destinations includes the plurality of line cards.

27. The packet switch of claim 24, wherein the packet switch includes a plurality of input interfaces;

and wherein the plurality of destinations includes the plurality of input interfaces.

28. The packet switch of claim 24, wherein the switch element is a routing stage switch element of the packet switch.

29. The packet switch of claim 24, wherein the switch element is a second stage switch element of a three stage switching fabric of the packet switch.