Switching device with multistage queuing scheme

• US 6,920,146 B1
• Filed: 10/05/1998
• Issued: 07/19/2005
• Est. Priority Date: 10/05/1998
• Status: Expired due to Term

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Packet Engines, Inc. (Nokia Corporation)
• Inventors: Michels, Timothy S, Davis, Greg W., Johnson, C Stuart
• Primary Examiner(s): Pham, Chi
• Assistant Examiner(s): ABELSON, RONALD B
• Application Number:
  US09/166,343
• Time in Patent Office: 2,479 Days
• Field of Search: 370/413, 370/415, 370/389, 370/392, 370/429, 370/378, 370/381, 370/395, 370/414, 370/356, 370/363, 370/368, 370/379, 370/412, 370/428, 710/53
• US Class Current: 370/415
• CPC Class Codes: H04L 12/18 for broadcast or conference , e.g. multicast
• CPC Class Codes: H04L 49/201 Multicast operation; Broadcast operation
• CPC Class Codes: H04L 49/205 Quality of Service based
• CPC Class Codes: H04L 49/25 Routing or path finding in a switch fabric
• CPC Class Codes: H04L 49/30 Peripheral units, e.g. input or output ports
• CPC Class Codes: H04L 49/351 for local area network [LAN], e.g. Ethernet switches
• CPC Class Codes: H04L 49/90 Buffering arrangements

Abstract

In a switching device, a method of communicating data packets from sending ports to destination ports includes storing in a first stage queue packet-related data from a sending port; determining from the packet-related data which destination ports are to receive the packet-related data in the first stage queue; storing in a second stage queue associated with each determined destination port the packet-related data from the first stage queue; and using the packet-related data in the second stage queue to complete the communication of the data packet from the sending port to each determined destination port. Apparatus for practicing the method comprises a first stage queue storing packet-related data from a sending port; and a second stage queue associated with each of a set of destination ports storing the packet-related data from the first stage queue.

Claims

1. In a switching device, apparatus for communicating data packets from sending ports to destination ports, comprising:

a first stage queue comprising a plurality of first queues for storing packet-related data from a sending port, wherein the packet-related data is stored in the plurality of first queues based on a characteristic of the data packets;

a second stage queue associated with each of a set of destination ports, the second stage queue comprising a plurality of second queues, each of the plurality of second queues for storing the packet-related data from each of the plurality of first queues of the first stage queue based on a characteristic of the data packets; and

a switch fabric coupled to the second stage queue, the switch fabric using the packet-related data in the second stage queue for transmitting the data packets to a destination port.

2. The apparatus of claim 1 including means for determining from the packet-related data which destination ports are to receive the packet-related data in the first stage queue.

3. The apparatus of claim 1 including address resolution logic sending the packet-related data from the sending port to the first stage queue.

4. The apparatus of claim 1 wherein each second stage queue includes multiple second queues, the packet-related data stored in a specific second queue based on the characteristic of the data packets.

5. The apparatus of claim 1 wherein the switch fabric is a shared memory switch fabric for communicating data packets from sending ports to destination ports.

6. The apparatus of claim 1 wherein the switch fabric is a crossbar matrix for communicating data packets from sending ports to destination ports.

7. In a switching device, a method for communicating data packets from sending ports to destination ports, the method comprising:

storing in a first stage queue a pointer to memory storing a data packet and a list of destination ports;

identifying a destination port stored in the first stage queue;

retrieving the pointer to memory stored in the first stage queue;

storing in a second stage queue associated with the identified destination port the retrieved pointer to memory; and

using the pointer to memory in the second stage queue to complete the communication of the data packet from the sending port to the identified destination port.

8. The method of claim 7, wherein the first stage queue includes multiple first queues, and the step of storing the pointer to memory in the first stage queue comprises storing the pointer in a specific first queue based on a characteristic of the packet.

9. The method of claim 7, wherein the second stage queue includes multiple second queues, and the step of storing the retrieved pointer to memory in the second stage queue comprises storing the retrieved pointer in a specific second queue based on a characteristic of the packet.

10. In a switching device, a method of communicating data packets from one or more sending ports to destination ports, the method comprising:

storing, in a first stage queue comprising a plurality of first queues, packet-related data associated with the data packets from the one or more sending ports, wherein the packet-related data are stored in one of the plurality of first queues based on a characteristic of the data packets;

determining from the packet-related data which destination ports are to receive the packet-related data in the first stage queue;

storing in a second stage queue associated with each determined destination port the packet-related data from the first stage queue; and

transmitting the packet-related data in the second stage queue to a switch fabric for completing the communication of the data packet from the sending port to each determined destination port.

11. The method of claim 10 wherein the switch fabric is a shared-memory switch fabric, and the transmitting comprises using the packet-related data to obtain a copy of the data packets from the shared-memory switch fabric to complete communication of the data packet.

12. The method of claim 10 wherein the switch fabric is a crossbar matrix, and the transmitting comprises using the packet-related data to form connections in the matrix so as to communicate simultaneously a copy of the data packets from the sending port to each of the determined destination ports.

13. In a switching device, a method of communicating data packets from sending ports to destination ports, the method comprising:

storing in a first stage queue packet-related data from a sending port;

determining from the packet-related data which destination ports are to receive the packet-related data in the first stage queue;

storing in a second stage queue associated with each determined destination port the packet-related data from the first stage queue based on network protocol type; and

transmitting the packet-related data in the second stage queue to a switch fabric for completing the communication of the data packet from the sending port to each determined destination port.

14. In a switching device, a method of communicating data packets from sending ports to destination ports, the method comprising:

storing in a first stage queue packet-related data from a sending port;

determining from the packet-related data which destination ports are to receive the packet-related data in the first stage queue;

storing in a second stage queue associated with each determined destination port the packet-related data from the first stage queue based on whether the data packets are unicast packets or multicast packets; and

transmitting the packet-related data in the second stage queue to a switch fabric for completing the communication of the data packet from the sending port to each determined destination port.

15. In a switching device, a method of communicating data packets from sending ports to destination ports, the method comprising:

storing in a first stage queue the data packets from a sending port;

determining from the data packets which destination ports are to receive the data packets in the first stage queue;

storing in a second stage queue associated with each determined destination port the data packets from the first stage queue based on a characteristic of the data packets; and

transmitting the data packets in the second stage queue to a switch fabric for completing the communication of the data packet from the sending port to each determined destination port.

16. A multistage queuing apparatus for transmitting data packets from one or more sending ports to a plurality of destination ports, comprising:

a first queue structure, operatively coupled to the one or more sending ports, comprising a plurality of first queues for storing packet-related data associated with the data packets based on a first characteristic of the data packets; and

a second queue structure, operatively coupled to the first queue structure and plurality of destination ports, comprising a plurality of second queues for storing the packet-related data based on the first characteristic and a second characteristic.

17. The multistage queuing apparatus of claim 16, wherein the first characteristic is priority.

18. The multistage queuing apparatus of claim 16, wherein the first characteristic is network protocol type.

19. The multistage queuing apparatus of claim 16, wherein the first characteristic is type of service.

20. The multistage queuing apparatus of claim 16, wherein the second characteristic is a destination port number associated with the plurality of destination ports.

21. A multistage queuing apparatus for transmitting data packets from one or more sending ports to a plurality of destination ports, comprising:

a first queue structure, operatively coupled to the one or more sending ports, comprising a first array of two or more first queues for storing the packet-related data associated with the data packets in accordance with a first characteristic of the data packets; and

a second queue structure comprising a plurality of second arrays, each of the second arrays comprising two or more second queues operatively coupled to one of the plurality of destination ports, wherein each of the second arrays is adapted to store the packet-related data from the first queue structure in accordance with the first characteristic.

22. The multistage queuing apparatus of claim 21, wherein the dimension of the first array is the same as the dimension of each of the plurality of second arrays.

23. The multistage queuing apparatus of claim 21, wherein the apparatus further includes port determination logic interposed between the first queue structure and second queue structure to determine to which of the plurality of destination ports to transmit the packet-related data.

24. In a switching device, a method of communicating data packets from sending ports to destination ports, the method comprising:

storing in a first stage queue packet-related data from a sending port based on a characteristic of the data packets;

determining from the packet-related data which destination ports are to receive the packet-related data in the first stage queue;

storing in a second stage queue associated with each determined destination port the packet-related data from the first stage queue; and

transmitting the packet-related data in the second stage queue to a switch fabric for completing the communication of the data packet from the sending port to each determined destination port.

25. The method of claim 24 wherein the packet-related data comprises a pointer to memory.

26. The method of claim 24 wherein the packet-related data is a data packet.

27. The method of claim 24 wherein the first stage queue comprises a plurality of first queues, and the step of storing the packet-related data in the first stage queue comprises storing the packet-related data in one of the plurality of first queues based on the characteristic of each of the data packets.

28. The method of claim 24 wherein the packet characteristic is priority.

29. The method of claim 24 wherein the packet characteristic is network protocol type.

30. The method of claim 24 wherein the packet characteristic is type of service.

31. The method of claim 24 wherein the packet characteristic is packet type comprising a unicast type and multicast type.