Switch module memory structure and per-destination queue flow control for use in a switch

• US 20050002410A1
• Filed: 02/11/2004
• Published: 01/06/2005
• Est. Priority Date: 06/19/2003
• Status: Active Grant

• Current Assignee: Polytechnic University (New York University)
• Original Assignee: Polytechnic University (New York University)
• Inventors: Park, Jinsoo, Chao, Hung-Hsiang Jonathan
• Granted Patent: US 7,792,118 B2
• Time in Patent Office: Days
• US Class Current: 370/412
• CPC Class Codes: H04L 49/1523 Parallel switch fabric planes
• CPC Class Codes: H04L 49/506 Backpressure

Abstract

To use the memory space more effectively, cell memory can be shared by an input link and all output links. To prevent one flow from occupying the entire memory space, a threshold may be provided for the queue. The queue threshold may accommodate the RTT delay of the link. Queue length information about a downstream switch module may be sent to an upstream switch module via cell headers in every credit update period per link. Cell and/or credit loss may be recovered from. Increasing the credit update period reduces the cell header bandwidth but doesn'"'"'t degrade performance significantly. Sending a credit per link simplifies implementation and eliminates interference between other links.

Claims

1. Apparatus for use with a switch module including a first plurality N of input links and a second plurality M of output links, the apparatus comprising a first plurality of buffers, each of the buffers shared by queues corresponding to each of the M output links, and each of the buffers being associated with a particular one of the input links.

2. The apparatus of claim 1 wherein each of the buffers is further shared by a multicast queue.

3. The apparatus of claim 1 wherein each of the buffers receives at most one cell per time slot.

4. The apparatus of claim 1 wherein the buffer size is less than M cells.

5. The apparatus of claim 1 wherein the buffer size is less than M/2 cells.

6. The apparatus of claim 1 wherein the switch module supports P priority levels, wherein the number of buffers is P*N.

7. The apparatus of claim 6 wherein the size of each buffer is less than M cells.

8. The apparatus of claim 6 wherein the size of each buffer is less than M/2 cells.

9. The apparatus of claim 1 wherein each buffer is adapted to send, at most, M cells per time slot.

10. The apparatus of claim 1 wherein each buffer has a read speed of no less than 6.2 n sec.

11. The apparatus of claim 1 wherein an average number of reads from a buffer is matched to output link utilization.

12. A method for controlling sending cells from a first device having at least one communications link with a second device, the second device being capable of maintaining, for each of the at least one communications links, a queue for each of a plurality of X destinations, the method comprising:

a) maintaining a cell count associated with each of the X destination queues of the second device;

b) accepting a cell at the first device;

c) determining a destination of the cell; and

d) determining whether or not to forward the cell from the first device to the second device using the cell count associated with the one of the X destination queues of the second device corresponding to the determined destination of the cell.

13. The method of claim 12 wherein acts (a)-(d) are preformed for each of the at least one communications links independently.

14. The method of claim 12 wherein the act of maintaining a cell count associated with each of the X destination queues of the second device includes, for each of the at least one communications link,

i) accepting credit update information originating from the second device;

ii) accepting cell-in-transit information concerning a number of cells in transit from the first device to the second device; and

iii) updating the cell count using the accepting credit update information and the accepted cell-in-transit information.

15. The method of claim 14 wherein the credit update information includes information about a number of cells in each of the destination queues of the second device associated with the at least one communications link.

16. The method of claim 14 wherein the credit update information includes a count of cells in each of the destination queues of the second device associated with the at least one communications link.

17. The method of claim 14 wherein the cell-in-transmit information is based on a round trip time delay between the first device and the second device.

18. The method of claim 14 further comprising:

iv) resetting cell-in-transit information concerning a number of cells in transit from the first device to the second device.

19. The method of claim 18 wherein the cell-in-transit information is reset after updating the cell count.

20. The method of claim 14 wherein the accepted credit update information originating from the second device is carried in a cell header.

21. The method of claim 14 wherein the accepted credit update information for all of the destination queues is separated into parts, and wherein each of the parts of the accepted credit update information are carried in a cell header of each of a plurality of S cells.

22. The method of claim 12 wherein the queues for the plurality of X destinations share a common buffer memory.

23. The method of claim 12 wherein the act of maintaining a cell count associated with each of the X destination queues of the second device includes, for each of the at least one communications link,

i) accepting per destination queue cell count information originating from the second device;

ii) accepting per destination queue cell-in-transit from the first device to the second device count; and

iii) updating a per destination queue cell count with a sum of (A) the per destination queue cell count and (B) the per destination queue cell-in-transit count.

24. The method of claim 23 wherein the credit update information includes information about a number of cells in each of the destination queues of the second device associated with the at least one communications link.

25. The method of claim 23 wherein the credit update information includes a count of cells in each of the destination queues of the second device associated with the at least one communications link.

26. The method of claim 23 wherein the cell-in-transmit information is based on a round trip time delay.

27. The method of claim 23 further comprising:

iv) resetting cell-in-transit information concerning a number of cells in transit from the first device to the second device.

28. The method of claim 27 wherein the cell-in-transit information is reset after updating the cell.

29. The method of claim 23 wherein the accepted credit update information originating from the second device is carried in a cell header.

30. The method of claim 23 wherein the accepted credit update information for all of the destination queues is separated into parts, and wherein each of the parts of the accepted credit update information are carried in a cell header of each of a plurality of S cells.

31. The method of claim 12 wherein the first device is an upstream switch module and the second device is a downstream switch module.

32. The method of claim 12 further comprising adding the cell to one of a plurality of destination output queues based on the determined destination of the cell,

wherein the act of determining whether or not to forward the cell from the first device to the second device is determined periodically for a head of line cell in each of the plurality of destination output queues.

33. The method of claim 21, wherein each of the plurality of S cells carries about R-bits of credit update information, wherein the maximum cell count size of each of the destination queues can be expressed with Q-bits, and wherein

34. The method of claim 21, wherein each of the plurality of S cells carries about R-bits of credit update information, wherein the maximum cell count size of each of the destination queues can be expressed with Q-bits, and wherein

35. The method of claim 30, wherein each of the plurality of S cells carries about R-bits of credit update information, wherein the maximum cell count size of each of the destination queues can be expressed with Q-bits, and wherein

36. The method of claim 30, wherein each of the plurality of S cells carries about R-bits of credit update information, wherein the maximum cell count size of each of the destination queues can be expressed with Q-bits, and wherein

37. Apparatus for controlling sending cells from a first device having at least one communications link with a second device, the second device being capable of maintaining, for each of the at least one communications links, a queue for each of a plurality of X destinations, the apparatus comprising:

a) means for maintaining a cell count associated with each of the X destination queues of the second device;

b) means for accepting a cell at the first device;

c) means for determining a destination of the cell; and

d) means for determining whether or not to forward the cell from the first device to the second device using the cell count associated with the one of the X destination queues of the second device corresponding to the determined destination of the cell.

38. The apparatus of claim 37 wherein the means for maintaining a cell count associated with each of the X destination queues of the second device include, for each of the at least one communications link,

i) means for accepting credit update information originating from the second device;

ii) means for accepting cell-in-transit information concerning a number of cells in transit from the first device to the second device; and

iii) means for updating the cell count using the accepting credit update information and the accepted cell-in-transit information.

39. The apparatus of claim 38 wherein the credit update information includes information about a number of cells in each of the destination queues of the second device associated with the at least one communications link.

40. The apparatus of claim 38 wherein the credit update information includes a count of cells in each of the destination queues of the second device associated with the at least one communications link.

41. The apparatus of claim 38 wherein the cell-in-transmit information is based on a round trip time delay between the first device and the second device.

42. The apparatus of claim 38 further comprising:

iv) means for resetting cell-in-transit information concerning a number of cells in transit from the first device to the second device.

43. The apparatus of claim 42 wherein the means for resetting reset cell-in-transit information after the cell count has been updated.

44. The apparatus of claim 38 wherein the accepted credit update, information originating from the second device is carried in a cell header.

45. The apparatus of claim 38 wherein the accepted credit update information for all of the destination queues is separated into parts, and wherein each of the parts of the accepted credit update information are carried in a cell header of each of a plurality of S cells.

46. The apparatus of claim 37 wherein the queues for the plurality of X destinations share a common buffer memory.

47. The apparatus of claim 37 wherein the means for maintaining a cell count associated with each of the X destination queues of the second device includes, for each of the at least one communications link,

i) accepts per destination queue cell count information originating from the second device;

ii) accepts per destination queue cell-in-transit from the first device to the second device count; and

iii) updates a per destination queue cell count with a sum of (A) the per destination queue cell count and (B) the per destination queue cell-in-transit count.

48. The apparatus of claim 47 wherein the credit update information includes information about a number of cells in each of the destination queues of the second device associated with the at least one communications link.

49. The apparatus of claim 47 wherein the credit update information includes a count of cells in each of the destination queues of the second device associated with the at least one communications link.

50. The apparatus of claim 47 wherein the cell-in-transmit information is based on a round trip time delay.

51. The apparatus of claim 47 further comprising:

iv) means for resetting cell-in-transit information concerning a number of cells in transit from the first device to the second device.

52. The apparatus of claim 51 wherein means for resetting reset the cell-in-transit information after the cell has been updated.

53. The apparatus of claim 47 wherein the accepted credit update information originating from the second device is carried in a cell header.

54. The apparatus of claim 47 wherein the accepted credit update information for all of the destination queues is separated into parts, and wherein each of the parts of the accepted credit update information are carried in a cell header of each of a plurality of S cells.

55. The apparatus of claim 37 wherein the first device is an upstream switch module and the second device is a downstream switch module.

56. The apparatus of claim 37 further comprising means for adding the cell to one of a plurality of destination output queues based on the determined destination of the cell,

wherein the means for determining whether or not to forward the cell from the first device to the second device operates periodically on a head of line cell in each of the plurality of destination output queues.

57. The apparatus of claim 45, wherein each of the plurality of S cells carries about R-bits of credit update information, wherein the maximum cell count size of each of the destination queues can be expressed with Q-bits, and wherein

58. The apparatus of claim 45, wherein each of the plurality of S cells carries about R-bits of credit update information, wherein the maximum cell count size of each of the destination queues can be expressed with Q-bits, and wherein

59. The apparatus of claim 54, wherein each of the plurality of S cells carries about R-bits of credit update information, wherein the maximum cell count size of each of the destination queues can be expressed with Q-bits, and wherein

60. The apparatus of claim 54, wherein each of the plurality of S cells carries about R-bits of credit update information, wherein the maximum cell count size of each of the destination queues can be expressed with Q-bits, and wherein