Weighted fair share scheduler for large input-buffered high-speed cross-point packet/cell switches

• US 20030227932A1
• Filed: 01/09/2003
• Published: 12/11/2003
• Est. Priority Date: 06/10/2002
• Status: Active Grant

• Current Assignee: Tahoe Research Limited (f/k/a Learndale Limited) (Vector Capital Corporation)
• Original Assignee: Velio Communications, Inc. (Broadcom, Inc.)
• Inventors: Dally, William J., Meempat, Gopalakrishnan, Ramamurthy, Gopalakrishnan
• Granted Patent: US 7,292,594 B2
• Time in Patent Office: Days
• US Class Current: 370/415
• CPC Class Codes: H04L 49/101 using crossbar or matrix
• 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

Abstract

A switching fabric connects input ports to output ports. Each input has an input pointer referencing an output port, and each output has an output pointer referencing an input port. An arbiter includes input and output credit allocators, and an arbitration module (matcher). The input credit allocator resets input credits associated with input/output pairs and updates the input pointers. Similarly, the output credit allocator resets output credits associated with input/output pairs and updates the output pointers. The matcher matches inputs to outputs based on pending requests and available input and output credits. A scheduler schedules transmissions through the cross-bar switch according to the arbiter'"'"'s matches.

Claims

1. A high-speed input buffered packet switch, comprising:

a switching fabric which connects input ports to output ports;

for each input port, an input pointer which references an output port;

for each output port, an output pointer which references an input port;

an arbiter, comprising;

an input credit allocator which resets input credits associated with input/output pairs and which updates the input pointers,

an output credit allocator which resets output credits associated with input/output pairs and which updates the output pointers, and

a matcher which matches inputs to outputs based on pending requests and available input and output credits; and

a scheduler which schedules transmissions through the switching fabric according to the arbiter'"'"'s matches.

2. The packet switch of claim 1, the input credit allocator, for each input, resetting input credits associated with the input and an output referenced by the input'"'"'s input pointer, said input credits being set to a weight value associated with said input/output pair when any of certain conditions are true, the input credit allocator also advancing the input pointer.

3. The packet switch of claim 2, wherein the certain conditions are any of:

said input/output pair has no input credits; and

there are no pending requests to connect the input/output pair through the switch.

4. The packet switch of claim 3, wherein the condition that there are no pending requests is further limited by the condition that the referenced output is available.

5. The packet switch of claim 1, the output credit allocator, for each output, resetting output credits associated with the output and an input referenced by the output'"'"'s output pointer, said output credits being set to a weight value associated with said input/output pair when any of certain conditions are true, the output credit allocator also advancing the output pointer.

6. The packet switch of claim 5, wherein the certain conditions are any of:

said input/output pair has no output credits; and

there are no pending requests to connect the input/output pair through the switch.

7. The packet switch of claim 6, wherein the condition that there are no pending requests is further limited by the condition that the referenced input is available.

8. The packet switch of claim 1, wherein the input pointers and output pointers are round-robin pointers.

9. The packet switch of claim 1, the matcher comprising:

a pre-selector which selects input ports for possible matching to output ports; and

a binder which binds at least some of the selected input ports to the output ports for which the input ports were selected.

10. The packet switch of claim 9, wherein the pre-selector and binder are executed serially in plural iterations.

11. The packet switch of claim 9, the pre-selector and binder pre-selecting and binding inputs and outputs having at least one credit.

12. The packet switch of claim 11, the pre-selector and binder pre-selecting and then binding inputs and outputs without credits, once no more pairs with credits can be found.

13. The packet switch of claim 12, wherein a borrow count is associated with the input/output pair to track borrowed credits when input-output matches are made without credits for the input/output pair.

14. The packet switch of claim 13, further comprising:

a set of input borrow counters for tracking borrowed input credits; and

a set of output borrow counters for tracking borrowed output credits,

the input borrow counters and output borrow counters operating in conjunction with the input and output credit counters.

15. The packet switch of claim 14, further comprising:

a common bit space dynamically shared between the borrow and credit counters at each output for each inbound stream, and at each input for each outbound stream.

16. The packet switch of claim 15, further comprising:

hardware logic which dynamically locates a boundary between credit and borrow fields based on the most significant non-zero bit of an associated weights register, during all manipulations involving credit and borrow counters.

17. The packet switch of claim 1, further comprising:

a request generator which, for each unlocked input port, sends a request to every output port for which the input port has a packet/cell awaiting transmission.

18. The packet switch of claim 1, packets being of variable length, further comprising:

a connection manager which monitors on-going traffic between inputs and outputs, and which updates the input and output credits based on the on-going traffic.

19. The packet switch of claim 18, further comprising:

a set of input and output lock indicators associated with the inputs and outputs that indicate establishment of connections, and that are maintained across multiple time slots over packet transmissions.

20. The packet switch of claim 19, further comprising:

a set of end-of-packet (EoP) indicators, each EoP indicator for indicating an end of transmission of a packet through an input associated with the EoP indicator, the connection manager resetting lock indicators associated with the input and output through which the packet is being transmitted, thereby releasing ports corresponding to the reset lock indicators for further arbitration.

21. The packet switch of claim 18, the connection manager, for each input transmitting a packet, decrementing the input and output credits associated with inputs and outputs through which transmissions are on-going, and detecting ends of packets.

22. The packet switch of claim 18, further comprising:

a start of packet (SoP) indicator associated with each input port, each SoP indicator being set by its associated input port when a first byte of a packet transmitted from said input port reaches the switching fabric, the SoP indicators being monitored by the connection manager, decrementing of a credit by the connection manager being delayed until the associated SoP indicator is set.

23. The packet switch of claim 1, further comprising:

a set of output credit registers to track output credits; and

a set of input credit registers to track input credits.

24. The packet switch of claim 1, packets being fixed-size cells, the arbiter

resetting input and output lock indicators at each time slot beginning, and

decrementing credit for admitted cell transmissions.

25. The packet switch of claim 24, wherein the arbiter further increments borrow counts for admitted cell transmissions.

26. The packet switch of claim 1, further comprising:

“

camp on”

logic which issues requests in anticipation of completion.

27. The packet switch of claim 26, the arbiter using “

unlocked”

, “

available” and

“

locked”

status modes for each input, an “

available”

input being an input through which a packet is currently transmitting but which has not been scheduled for a next transmission, any input that initiates a fresh packet transmission transitioning into the “

available”

state, and once matched, transitioning to the “

locked”

state, and remaining in the “

locked”

state until the end of an on-going transmission.

28. The packet switch of claim 26, the arbiter using “

unlocked”

, “

available” and

“

locked”

status modes for each input and output, upon receipt of a start schedule (Ssch) signal at an input, the input transitioning into the “

available”

state, the Ssch signal being issued from a corresponding input module a fixed number of slots prior to an end of its ongoing packet transmission, and the output currently receiving the packet also transitioning into the “

available”

state.

29. The packet switch of claim 1, wherein the switching fabric is a crossbar switch.

30. A method for high-speed input buffered packet switching, comprising:

providing a switching fabric for connecting input ports to output ports;

for each input port, maintaining an input pointer which references an output port;

for each output port, maintaining an output pointer which references an input port;

in an arbiter,

resetting input credits and output credits associated with input/output pairs,

updating the input pointers and output pointers,

matching inputs to outputs based on pending requests and available input and output credits; and

in a scheduler, scheduling transmissions through the cross-bar switch according to the matching.

31. The method of claim 30, further comprising, for each input:

resetting input credits associated with the input and an output referenced by the input'"'"'s input pointer, said input credits being set to a weight value associated with said input/output pair when any of certain conditions are true; and

advancing the input pointer.

32. The method of claim 31, wherein the certain conditions are any of:

said input/output pair has no input credits; and

there are no pending requests to connect the input/output pair through the switch.

33. The method of claim 32, wherein the condition that there are no pending requests is further limited by the condition that the referenced output is available.

34. The method of claim 30, further comprising, for each output:

resetting output credits associated with the output and an input referenced by the output'"'"'s output pointer, said output credits being set to a weight value associated with said input/output pair when any of certain conditions are true; and

advancing the output pointer.

35. The method of claim 34, wherein the certain conditions are any of:

said input/output pair has no output credits; and

there are no pending requests to connect the input/output pair through the switch.

36. The method of claim 35, wherein the condition that there are no pending requests is further limited by the condition that the referenced input is available.

37. The method of claim 30, wherein the input pointers and output pointers are round-robin pointers.

38. The method of claim 30, the arbiter further:

selecting input ports for possible matching to output ports; and

binding at least some of the selected input ports to the output ports for which the input ports were selected.

39. The method of claim 38, the steps of selecting and binding being executed serially in plural iterations.

40. The method of claim 38, the steps of selecting and binding being performed upon inputs and outputs having at least one credit.

41. The method of claim 40, the steps of selecting and binding being performed upon inputs and outputs without credits, once no more pairs with credits can be found.

42. The method of claim 41, further comprising:

associating a borrow count with the input/output pair to track borrowed credits when input-output matches are made without credits for the input/output pair.

43. The method of claim 42, further comprising:

maintaining a set of input borrow counters for tracking borrowed input credits; and

maintaining a set of output borrow counters for tracking borrowed output credits,

the input borrow counters and output borrow counters operating in conjunction with the input and output credit counters.

44. The method of claim 43, further comprising:

dynamically sharing a common bit space between the borrow and credit counters at each output for each inbound stream, and at each input for each outbound stream.

45. The method of claim 44, further comprising:

dynamically locating, with hardware logic, a boundary between credit and borrow fields based on the most significant 1 bit of an associated weights register, during all manipulations involving credit and borrow counters.

46. The method of claim 30, further comprising:

for each unlocked input port, sending a request to every output port for which the input port has a packet/cell awaiting transmission.

47. The method claim 30, packets being of variable length, the method further comprising:

monitoring, in a connection manager, on-going traffic between inputs and outputs, and updating the input and output credits based on the on-going traffic.

48. The method of claim 47, further comprising:

maintaining across multiple time slots over packet transmissions a set of input and output lock indicators associated with the inputs and outputs that indicate establishment of connections.

49. The method of claim 48, further comprising:

maintaining a set of end-of-packet (EoP) indicators, each EoP indicator for indicating an end of transmission of a packet through an input associated with the EoP indicator, the connection manager resetting lock indicators associated with the input and output through which the packet is being transmitted, thereby releasing ports corresponding to the reset lock indicators for further arbitration.

50. The method of claim 47, the connection manager further:

for each input transmitting a packet, decrementing the input and output credits associated with inputs and outputs through which transmissions are on-going; and

detecting ends of packets.

51. The method of claim 47, further comprising:

associating a start of packet (SoP) indicator with each input port;

setting, by its associated input port, each SoP indicator when a first byte of a packet transmitted from said input port reaches the switching fabric;

monitoring, by the connection manager, the SoP indicators, decrementing of a credit being delayed until the associated SoP indicator is set.

52. The method of claim 30, further comprising:

maintaining a set of output credit registers to track output credits; and

maintaining a set of input credit registers to track input credits.

53. The method of claim 30, packets being fixed-size cells, further comprising:

in the arbiter,

resetting input and output lock indicators at each time slot beginning, and

decrementing number of credits for admitted cell transmissions.

54. The method of claim 53, the arbiter manipulating borrows.

55. The method of claim 30, further comprising:

issuing requests in anticipation of completion.

56. The method of claim 55, further comprising:

using “

unlocked”

, “

available” and

“

locked”

status modes for each input, an “

available”

input being an input through which a packet is currently transmitting but which has not been scheduled for a next transmission, any input that initiates a fresh packet transmission transitioning into the “

available”

state, and once matched, transitioning to the “

locked”

state, and remaining in the “

locked”

state until the end of an on-going transmission.

57. The method of claim 55, further comprising:

using “

unlocked”

, “

available” and

“

locked”

status modes for each input and output, upon receipt of a start schedule (Ssch) signal at an input, the input transitioning into the “

available”

state, the Ssch signal being issued from a corresponding input module a fixed number of slots prior to an end of its ongoing packet transmission, and the output currently receiving the packet also transitioning into the “

available”

state.

58. A method for high-speed input buffered packet switching, comprising:

for each input port;

associating a pointer with said port, the pointer referencing an output port, and

associating, with said port, plural credit counters corresponding to different output ports;

for each output port;

associating a pointer with said port, the pointer referencing an input port, and

associating, with said port, plural credit counters corresponding to different input ports; and

during each time slot;

for each input port not carrying traffic, if the associated credit counter corresponding to the output port referenced by the pointer associated with the input port has zero credits, reloading said credit counter with a specified weight and advancing the pointer,

for each output port not carrying traffic, if the associated credit counter corresponding to the input port referenced by the pointer associated with the output port has zero credits, reloading said credit counter with a specified weight and advancing the pointer,

selecting input-output paths for connection based on pending requests and credit counter values,

for each selected input-output path, decrementing appropriate input port and output port credit counters.

59. The method of claim 58, further comprising, during each time slot:

for each input (output) port not carrying traffic, reloading said credit counter with a specified weight, and advancing the associated pointer, if

i) the associated credit counter corresponding to the output port referenced by the pointer associated with the input port has positive credits,

ii) there are no pending requests between the input port and the output port, and

iii) if the referenced output port is free; and

for each output port not carrying traffic, reloading said credit counter with a specified weight, and advancing the associated pointer, if

i) the associated credit counter corresponding to the input port referenced by the pointer associated with the output port has positive credits,

ii) there are no pending requests between the output port and the input port, and

iii) if the referenced input port is free.

60. A high-speed input buffered packet switch, comprising:

a switching fabric for connecting input ports to output ports;

an arbiter which allocates input credits and output credits to input/output pairs, updates pointers associated with each input and output, and performs arbitration; and

a connection manager which monitors ongoing packet transmissions through the switch, and which performs credit decrements for each input and output involved in an ongoing transmission, the arbiter and connection manager being executed at each of plural time slots.

61. The switch of claim 60, wherein the arbiter and connection manager execute independently during each time slot.

62. The switch of claim 60, wherein the arbiter performs arbitration by iteratively executing a pre-select phase followed by a bind phase, during the pre-select phase of each iteration, every unlocked output that has received at least one pending request pre-selects one of the requesting inputs, and during the bind phase, each input that has been pre-selected by at least one output port locks in on one of said output ports.

63. A high-speed input buffered packet switch, comprising:

a switching fabric which connects input ports to output ports;

a processing module associated with each input port and a processing module associated with each output port, each processing module executing independently of the other processing modules,

each output processing module maintaining an output credit count for each input port and, responsive to requests from the input ports and the output credit counts, preselecting one of the requesting input ports according to a fairness algorithm,

each input processing module maintaining an input credit count for each output port and, responsive to the preselections and the input credit counts, binding the input port to one of its preselecting output ports according to a fairness algorithm; and

a scheduler which schedules transmissions through the switching fabric according to the bindings.

64. The switch of claim 63, wherein the switching fabric is a crossbar switch.

65. The switch of claim 63,

each output processing module, if it has not been bound to its preselected input, responsive to the requests and the output credit counts, preselecting an unbound requesting input port according to a fairness algorithm, and

each unbound input processing module, responsive to the preselections and the input credit counts, binding the input port to one of its preselecting output ports according to a fairness algorithm.

66. The switch of claim 63, each processing module maintaining credit counts responsive to on-going variable-length packet transmissions through the associated input/output port.

67. The switch of claim 63, multiple switching fabrics operating in parallel.

68. The switch of claim 63, the processing modules executing on separate hardware processors.

69. The switch of claim 63, plural processing modules executing on a common hardware processor.

70. The switch of claim 63, credit counts including borrows incurred where a packet has been transmitted without credits.