Configurable virtual output queues in a scalable switching system

• US 7,046,687 B1
• Filed: 01/16/2002
• Issued: 05/16/2006
• Est. Priority Date: 01/16/2002
• Status: Expired due to Fees

• Current Assignee: Tau Networks Co.
• Original Assignee: Tau Networks Co.
• Inventors: Johnson, Peter, Lea, Chin-Tau, Brown, Philip Desborough Pritchard
• Primary Examiner(s): LEE, CHI HO A
• Application Number:
  US10/051,990
• Time in Patent Office: 1,581 Days
• Field of Search: None
• US Class Current: 370/412
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 47/6205 Arrangements for avoiding head of line blocking
• CPC Class Codes: H04L 49/1507 Distribute and route fabrics, e.g. sorting-routing or Batcher-Banyan
• CPC Class Codes: H04L 49/201 Multicast operation; Broadcast operation
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 49/3027 Output queuing
• CPC Class Codes: H04L 49/3045 Virtual queuing
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/901 using storage descriptor, e.g. read or write pointers

Abstract

Configurable virtual output queues (VOQs) in a scalable switching system and methods of using the queues are provided. The system takes advantage of the fact that not all VOQs are active or need to exist at one time. Thus, the system advantageously uses configurable VOQs and may not dedicate memory space and logic to all possible VOQs at one time.

Claims

1. A port processor configured to receive data packets from a line card, each data packet comprising a destination port address and data, the port processor comprising:

a random access memory (RAM) configured to store packets from the line card;

a content addressable memory (CAM) configured to store a plurality of entries, each CAM entry configured to comprise (a) a destination port address field and (b) a pointer field, wherein each CAM entry has a memory address corresponding to a memory location of the RAM;

a storage unit configured to store a plurality of queue entries, each queue entry configured to comprise (a) a destination port address of a set of one or more CAM entries, (b) a header pointer field equal to a pointer field of a first CAM entry in the set, and (c) a tail pointer field equal to a pointer field of a last CAM entry in the set; and

a controller configured to control the RAM, CAM and storage unit.

2. The port processor of claim 1, wherein the controller is configured to transfer packets from the line card to the RAM and transfer packets from the RAM to a switch fabric.

3. The port processor of claim 1, wherein the controller is configured to (a) receive a packet from the line card, (b) create a queue entry in the storage unit, the queue entry comprising a destination port address equal to a destination port address of the packet, (c) write an entry in the CAM, the CAM entry comprising the destination port address of the packet and a tail pointer field of the queue entry, and (d) store the packet in a location in the RAM corresponding to a memory address of the CAM entry.

4. The port processor of claim 3, wherein the controller is configured to create a new queue entry in the storage unit when the controller receives a packet with a destination port address that does not match a destination port address of any queue entry in the storage unit.

5. The port processor of claim 3, wherein the controller is further configured to increment the tail pointer field of the queue entry.

6. The port processor of claim 1, wherein the controller is configured to (a) receive a packet from the line card, (b) find a queue entry in the storage unit, the queue entry comprising a destination port address equal to a destination port address of the packet, (c) write an entry in the CAM, the CAM entry comprising the destination port address of the packet and a tail pointer field of the queue entry, and (d) store the packet in a location in the RAM corresponding to a memory address of the CAM entry.

7. The port processor of claim 6, wherein the controller is further configured to increment the tail pointer field of the queue entry.

8. The port processor of claim 1, wherein the controller is configured to send a schedule request to a scheduler, the schedule request based on a destination port address of a queue entry in the storage unit.

9. The port processor of claim 8, wherein the controller is further configured to increment a count field in the queue entry, the count field being equal to a number of schedule requests sent to the scheduler based on the destination port address of the queue entry.

10. The port processor of claim 1, wherein the controller is configured to (a) find a queue entry in the storage unit with a destination port address that matches a destination port address of a request grant from a scheduler, (b) send the destination port address and a head pointer field of the queue entry to the CAM, (c) receive a memory address of an entry in the CAM, the CAM entry having a destination port address and pointer field that match the destination port address and head pointer field of the queue entry, and (d) transfer a packet from a location in the RAM to a switch fabric, the location corresponding to the memory address of the CAM entry.

11. The port processor of claim 10, wherein the controller is further configured to increment the head pointer field of the queue entry.

12. The port processor of claim 11, wherein the controller is further configured to delete the queue entry if the head pointer field is equal to the tail pointer field.

13. The port processor of claim 10, wherein the controller is further configured to decrement a request count field in the queue entry, the count field being equal to a number of pending schedule requests sent to the scheduler based on the destination port address of the queue entry.

14. The port processor of claim 1, wherein the controller is configured to erase an entry in the CAM when the controller transfers a packet corresponding to the CAM entry from the RAM to a switch fabric.

15. A port processor configured to receive data packets from a line card, each data packet comprising a destination port address, a priority level and data, the port processor comprising:

a random access memory (RAM) configured to store packets from the line card;

a content addressable memory (CAM) configured to store a plurality of entries, each CAM entry configured to comprise (a) a destination port address field, (b) a priority level, and (c) a pointer field, wherein each CAM entry has a memory address corresponding to a memory location of the RAM;

a storage unit configured to store a plurality of queue entries, each queue entry configured to comprise (a) a destination port address of a set of one or more CAM entries, (b) a priority level of the set of one or more CAM entries, (c) a header pointer field equal to a pointer field of a first CAM entry in the set, and (d) a tail pointer field equal to a pointer field of a last CAM entry in the set; and

a controller configured to control the RAM, CAM and storage unit.

16. The port processor of claim 15, wherein the controller is configured to (a) receive a packet from the line card, (b) find a queue entry in the storage unit, the queue entry comprising a destination port address and a priority level equal to a destination port address and a priority level of the packet, (c) write an entry in the CAM, the CAM entry comprising the destination port address and priority level of the packet and a tail pointer field of the queue entry, and (d) store the packet in a location in the RAM corresponding to a memory address of the CAM entry.

17. The port processor of claim 15, wherein the controller is configured to send a schedule request to a scheduler, the schedule request based on a destination port address and a priority level of a queue entry in the storage unit.

18. The port processor of claim 15, wherein the controller is configured to (a) find a queue entry in the storage unit with a destination port address and a priority level that match a destination port address and a priority level of a request grant from a scheduler, (b) send the destination port address, priority level and a head pointer field of the queue entry to the CAM, (c) receive a memory address of an entry in the CAM, the CAM entry having a destination port address, priority level and pointer field that match the destination port address, priority level and head pointer field of the queue entry, and (d) transfer a packet from a location in the RAM to a switch fabric, the location corresponding to the memory address of the CAM entry.

19. A controller in a packet switching system, the controller being configured to (a) receive a packet from a line card, (b) find a queue entry in a storage unit, the queue entry comprising a destination port address equal to a destination port address of the packet, (c) write an entry in a content addressable memory (CAM), the CAM entry comprising the destination port address of the packet and a pointer value from the queue entry, and (d) store the packet in a location in a random access memory (RAM) corresponding to a memory address of the CAM entry.

20. The controller of claim 19, further configured to send a schedule request to a scheduler, the schedule request based on a destination port address of a queue entry in the storage unit.

21. The controller of claim 20, further configured to increment a count field in the queue entry, the count field being equal to a number of schedule requests sent to the scheduler based on the destination port address of the queue entry.

22. A controller in a packet switching system, the controller being configured to (a) find a queue entry in a storage unit with a destination port address that matches a destination port address of a request grant from a scheduler, (b) send the destination port address and a head pointer field of the queue entry to a content addressable memory (CAM), (c) receive a memory address of an entry in the CAM, the CAM entry having a destination port address and pointer field that match the destination port address and head pointer field of the queue entry, and (d) transfer a packet from a location in a random access memory (RAM) to a switch fabric, the location corresponding to the memory address of the CAM entry.

23. The controller of claim 22, wherein the controller is further configured to decrement a request count field in the queue entry, the count field being equal to a number of pending schedule requests sent to the scheduler based on the destination port address of the queue entry.

24. A content addressable memory (CAM) in a packet switching system, the CAM being configured to store a plurality of entries, each CAM entry configured to comprise (a) a destination port address and (b) a pointer field, each CAM entry having a memory address corresponding to a memory location of a random access memory (RAM), the CAM being configured to receive a destination port address and a pointer value and output a memory address of a CAM entry comprising the same destination port address and pointer value.

25. The CAM of claim 24, wherein each CAM entry further comprises a priority level, the CAM being configured to receive a destination port address, a priority level and a pointer value and output a memory address of a CAM entry comprising the destination port address, priority level and pointer value.

26. The CAM of claim 24, wherein each CAM entry further comprises a valid bit to indicate whether the entry currently corresponds to a packet stored in the RAM.

27. A storage unit in a packet switching system, the storage unit being configured to store a plurality of queue entries, each queue entry configured to comprise (a) a destination port address common to a set of one or more entries in a content addressable memory (CAM), (b) a header pointer field equal to a pointer field of a first entry in the set of CAM entries, and (c) a tail pointer field equal to a pointer field of a last entry in the set of CAM entries, the storage unit being configured to output the destination port address, header pointer and the tail pointer.

28. The storage unit of claim 27, wherein each queue entry is erasable to store a destination port address common to a new set of one or more entries in the CAM.

29. The storage unit of claim 27, wherein the head pointer field and the tail pointer field of each entry may be independently incremented.

30. The storage unit of claim 27, wherein each queue entry further comprises a priority level common to a set of one or more entries in a CAM.

31. The storage unit of claim 27, wherein each queue entry further comprises a request count field, the request count field being equal to a number of schedule requests sent to a scheduler based on the destination port address of the queue entry.

32. The storage unit of claim 27, wherein each queue entry further comprises a queue-over-limit field configured to indicate that a number of CAM entries in a set exceeds a pre-determined number.

33. The storage unit of claim 27, wherein each queue entry further comprises a queue-over-limit field configured to indicate that a number of pending schedule requests sent to a scheduler based on the destination port address of the queue entry exceeds a pre-determined number.

34. The storage unit of claim 27, wherein each queue entry further comprises a flow control bit configured to indicate whether a controller has initiated a flow control process for the destination port address of the queue entry.

35. A controller in a packet switching system, the controller being configured to (a) receive a multicast packet from a line card, the packet comprising data and a plurality of destination port addresses, (b) store an entry in a storage unit, the entry comprising the destination port addresses of the packet and an address of a location in a random access memory (RAM) configured to store the packet, and (c) store the packet in the location of the RAM.

36. The controller of claim 35, wherein the entry in the storage unit further comprises a flow control field configured to indicate whether any destination port address of the multicast packet has been flow-controlled.

37. The controller of claim 35, wherein the entry in the storage unit further comprises a packet requested field configured to indicate whether a request has been sent to a scheduler for any of the destination port addresses in the entry.

38. The controller of claim 35, wherein the entry in the storage unit further comprises a packet sent field configured to indicate whether the packet has been sent to any of the destination port addresses in the entry.

39. The controller of claim 35, wherein the entry in the storage unit further comprises a priority level field configured to indicate the priority level of the packet.

40. The controller of claim 35, further configured to send a plurality of schedule requests to a scheduler based on the plurality of destination port addresses of a multicast packet.

41. A storage unit in a packet switching system, the storage unit being configured to store a plurality of entries, each entry configured to comprise (a) a plurality of destination port addresses of a multicast packet and (b) an address of a location in a random access memory (RAM) configured to store the packet.

42. A method of managing a packet in a packet switching system, the method comprising:

creating a queue entry based on a destination port address of a packet received from a line card, the queue entry comprising the destination port address of the packet and a tail pointer value;

transferring the destination address and tail pointer value to an available entry in a content addressable memory (CAM); and

writing the packet to a location in a random access memory (RAM) that corresponds to an address of the entry in the CAM.

43. The method of claim 42, further comprising incrementing the tail pointer value of the queue entry.

44. A method of using a port processor in a packet switching system, the method comprising:

creating a queue entry based on a destination port address and a priority level of a packet received from a line card, the queue entry comprising the destination port address and priority level of the packet and a tail pointer value;

transferring the destination address, priority level and tail pointer value to an available entry in a content addressable memory (CAM); and

writing the packet to a location in a random access memory (RAM) that corresponds to an address of the entry in the CAM.

45. A method of processing a schedule request grant from a scheduler, the method comprises:

receiving a schedule request grant from a scheduler;

finding a queue entry in a storage unit with a destination port address that matches a destination port address of the schedule request grant;

sending the destination port address and a head pointer field of the queue entry to a content addressable memory (CAM);

receiving a memory address of an entry in the CAM, the CAM entry having a destination port address and pointer field that match the destination port address and head pointer field of the queue entry; and

transferring a packet from a location in a random access memory (RAM) to a switch fabric, the location corresponding to the memory address of the CAM entry.

46. A method of processing a multicast packet, the method comprising:

receiving a multicast packet from a line card, the packet comprising data and a plurality of destination port addresses;

storing an entry in a storage unit, the entry comprising the destination port addresses of the packet and an address of a location in a random access memory (RAM) configured to store the packet; and

storing the packet in the location of the RAM.