Backpressure mechanism for switching fabric Number:7,426,185 from the United States Patent and Trademark Office (PTO) owispatent

Title: Backpressure mechanism for switching fabric

Abstract: Roughly described, a packet switching fabric contains a separate queue scheduler for each combination of an input module and a fabric output port. The schedulers may also be specific to a single class of service. Each queue scheduler schedules its packets without regard to state of other input queues and without regard to packets destined for other output ports. In an aspect, the fabric manages per-flow bandwidth utilization of output port bandwidth capacity by monitoring the same and asserting backpressure toward the queue scheduler for any thread that is exceeding its bandwidth allocation. In another aspect, a switching fabric uses leaky buckets to apply backpressure in response to overutilization of downstream port capacity by particular subflows. In another aspect, a switching fabric includes a cascaded backpressure scheme.

Patent Number: 7,426,185 Issued on 09/16/2008 to Musacchio,   et al.

---

Inventors:	Musacchio; John T. (Berkeley, CA), Walrand; Jean (Berkeley, CA), Myers, Jr.; Roy T. (Santa Clara, CA), Parekh; Shyam P. (Orinda, CA), Mo; Jeonghoon (Sunnyvale, CA), Agarwal; Gaurav (San Jose, CA)
Assignee:	Agere Systems Inc. (Allentown, PA)
Appl. No.:	10/358,678
Filed:	February 5, 2003

---

Related U.S. Patent Documents

---

	Application Number	Filing Date	Patent Number	Issue Date
	60362144	Mar., 2002

---

Current U.S. Class:	370/235.1 ; 370/236; 709/234
Current International Class:	G01R 31/08 (20060101)

---

References Cited [Referenced By]

---

U.S. Patent Documents

5280470	January 1994	Buhrke et al.
5339332	August 1994	Kammerl
5367518	November 1994	Newman
5455826	October 1995	Ozveren et al.
5475682	December 1995	Choudhury et al.
5754120	May 1998	Argentati
5859835	January 1999	Varma et al.
5903735	May 1999	Kidder et al.
5923644	July 1999	McKeown et al.
5926459	July 1999	Lyles et al.
5930234	July 1999	Yoshida
5946297	August 1999	Calvignac et al.
6038217	March 2000	Lyles
6064650	May 2000	Kappler et al.
6064651	May 2000	Rogers et al.
6064677	May 2000	Kappler et al.
6078585	June 2000	Kakuma et al.
6101193	August 2000	Ohba
6134217	October 2000	Stiliadis et al.
6345040	February 2002	Stephens et al.
6359861	March 2002	Sui et al.
6388992	May 2002	Aubert et al.
6426944	July 2002	Moore
6683884	January 2004	Howard
6810031	October 2004	Hegde et al.
6810426	October 2004	Mysore et al.
7023841	April 2006	Dell et al.
7072345	July 2006	Siu et al.
7106699	September 2006	Barri
7139271	November 2006	Parruck et al.
2002/0012340	January 2002	Kalkunte et al.
2002/0012341	January 2002	Battle et al.
2002/0131413	September 2002	Tsao et al.

Foreign Patent Documents

	WO 00/64109		Oct., 2000		WO

Other References

C Clos, "A Study of Non-Blocking Switching Networks", Bell System Technical Journal, Mar. 1953, vol. 32, No. 3, pp. 406-424. cited by other . M. Shreedhar and G. Varghese, "Efficient Fair Queuing Using Deficit Round Robin," in Proceedings of ACM SIGCOMM'95, pp. 231-242 (1995). cited by other . Adiseshu, Hari, et al., "Reliable FIFO Load Balancing over Multiple FIFO Channels," WUCS-95-11, May 3, 1995, pp. 1-24. cited by other . Juniper Networks, Inc., "Supporting Differentiated Service Classes: Queue Scheduling Disciplines," 2001, pp. 1-27. cited by other . Adiseshu, Hari, et al. "A Reliable and Scalable Striping Protocol," Dept. of Computer Science, Washington University, St. Louis, MO, Jun. 3, 1996, 11 pages. cited by other.

Primary Examiner: Wilson; Robert W
Attorney, Agent or Firm: Mendelsohn & Associates Mendelsohn; Steve

---

Parent Case Text

---

CROSS-REFERENCES

This application claims the benefit of U.S. Provisional Application No. 60/362,144, filed Mar. 6, 2002, incorporated herein by reference in its entirety.

---

Claims

---

The invention claimed is:

1. Flow control apparatus comprising: an output port having an output port bandwidth; a first monitor that operates to monitor bandwidth utilization through said output port by a plurality of downstream-flowing information flows all sharing said output port bandwidth, and to assert a first backpressure signal in response to overutilization of said output port due to a first one of said information flows, said first backpressure signal being specific to said first information flow; a source of said information flows, said source upstream of the output port and that operates to withhold information from said output port of said first information flow in response to said first backpressure signal, until said first backpressure signal is withdrawn; and a feed-forward unit upstream of the first monitor and that operates to send signals downstream to said first monitor indicating numbers of blocks of said first information flow scheduled for downstream transmission as seen at a point upstream of said output port.

2. Apparatus according to claim 1, wherein said source comprises: a second monitor operable to monitor bandwidth utilization into said first flow by a plurality of sub-flows all sharing said first flow, and to assert a second backpressure signal in response to overutilization of said first flow due to a first one of said sub-flows; and a source of said sub-flows, said source operable to withhold from said first flow information from said first sub-flow in response to said second backpressure signal.

3. Apparatus according to claim 1, further comprising: a plurality of data paths operable to carry said first information to said output port; and a distribution unit for distributing packets of said first information flow among said data paths, wherein said feed-forward unit is operable to send signals to said first monitor indicating bandwidth utilization of said first information flow as seen at a point no farther downstream than said distribution unit.

4. Apparatus according to claim 3, wherein at least one of said data paths includes an information storage queue between said distribution unit and said output port.

5. Apparatus according to claim 1, wherein at least one data path carrying said first information flow includes at least one information storage queue upstream of said output port, and wherein said feed-forward unit is operable to send signals to said first monitor indicating bandwidth utilization of said first information flow as seen at a point upstream of said information storage queue.

6. Switching fabric apparatus comprising: a plurality of input ports; a plurality of output ports; data paths that operate to carry a plurality of information flows from said input ports to said output ports, said data paths operate to carry flows from more than one input port to each of said output ports; scheduling apparatus that operates to select next packets for transmission through each given one of said output ports from among the information flows destined for the given output port; and a plurality of monitors, each operates to monitor bandwidth utilization through a respective subset of said output ports, and to assert backpressure signals in response to overutilization of any of the output ports in said subset by any of the information flows destined for that output port, wherein: said plurality of monitors includes a particular monitor that operates to monitor bandwidth utilization through a particular subset of said output ports, said particular subset of output ports including a particular output port; said switching fabric apparatus is a multistage apparatus including a plurality of input modules in an input stage and a plurality of output modules in an output stage, said output ports being distributed across said output modules; and said particular monitor is not disposed in the module having said particular output port.

7. Apparatus according to claim 6, each of said monitors is operable to monitor bandwidth utilization through a respective one of said output ports.

8. Apparatus according to claim 6, comprising a plurality of output modules each having one of said output ports, wherein each of said monitors is operable to monitor bandwidth utilization through an output port on a respective one of said output modules.

9. Apparatus according to claim 6, wherein said switching fabric apparatus is a multistage apparatus including a plurality of input modules in an input stage, a plurality of output modules in an output stage, and a plurality of intermediate stage modules in an intermediate stage, said output ports being distributed across said output modules, said input ports being distributed across said input modules, and said monitors being distributed across more than one of said intermediate stage modules.

10. Apparatus according to claim 6, wherein said switching fabric apparatus is a multistage apparatus including a plurality of input modules in an input stage, a plurality of output modules in an output stage, and a plurality of intermediate stage modules in an intermediate stage, said output ports being distributed across said output modules, and said input ports being distributed across said input modules, wherein a particular one of said monitors is disposed in one of said intermediate stage modules.

11. Apparatus according to claim 6, wherein said switching fabric apparatus is a multistage apparatus including a plurality of input modules in an input stage, a plurality of output modules in an output stage, and a plurality of intermediate stage modules in an intermediate stage, said output ports being distributed across said output modules, and said input ports being distributed across said input modules, wherein a particular one of said monitors is disposed in a particular one of said intermediate stage modules, and wherein the information flows destined for one of the output ports the bandwidth utilization through which the particular monitor is operable to monitor, include at least one data packet that does not pass through said particular intermediate stage module.

12. Apparatus according to claim 6, wherein said plurality of monitors includes a particular monitor operable to monitor bandwidth utilization through a particular subset of said output ports, said particular subset of output ports including a particular output port, wherein said particular monitor is responsive to signals from a source upstream of said scheduling apparatus indicating bandwidth utilization of each of said information flows.

13. Apparatus according to claim 12, wherein said switching fabric apparatus is a multistage apparatus including a plurality of input modules in an input stage, wherein a first one of said information flows destined for said particular output port originates at a first one of said input modules, and wherein said source upstream of said scheduling apparatus is disposed on said first input module.

14. Apparatus according to claim 6, wherein said plurality of monitors includes a particular monitor operable to monitor bandwidth utilization through a particular subset of said output ports, said particular subset of output ports including a particular output port, wherein said switching fabric apparatus is a multistage apparatus including a plurality of input modules in an input stage, first and second ones of said information flows destined for said particular output port originating at first and second different ones of said input modules, and wherein said particular monitor is responsive to signals from a source in each of said first and second input modules indicating bandwidth utilization of each of said first and second information flows, respectively.

15. Apparatus according to claim 14, wherein said switching fabric apparatus further includes a plurality of output modules in an output stage, and a plurality of intermediate stage modules in an intermediate stage, said output ports being distributed across said output modules, wherein said particular monitor is disposed in a particular one of said intermediate stage modules.

16. Apparatus according to claim 15, wherein said first and second information flows collectively include information portions that do not flow through said particular intermediate stage module.

17. Apparatus according to claim 14, wherein said switching fabric apparatus further includes a plurality of output modules in an output stage, said output ports being distributed across said output modules and said particular output port being located on a particular one of said output modules, wherein said particular monitor is further responsive to signals from said particular output module indicating overall bandwidth utilization through said particular output port.

18. Apparatus according to claim 6, wherein said plurality of monitors includes a particular monitor operable to monitor bandwidth utilization through a particular subset of said output ports, said particular subset of output ports including a particular output port, wherein said switching fabric apparatus is a multistage apparatus including a plurality of input modules in an input stage, and a plurality of output modules in an output stage, said output ports being distributed across said output modules and said particular output port being located on a particular one of said output modules, wherein first and second ones of said information flows destined for said particular output port originate at respective different first and second ones of said input modules, and wherein said particular monitor is responsive to signals from said particular output module indicating overall bandwidth utilization through said particular output port.

19. Flow control apparatus comprising: a port; a microbundle leaky bucket for monitoring a microbundle flow through said port, said microbundle leaky bucket having a fill level that increases in response to information packets in said microbundle flow and reduces in accordance with a desired average microbundle data rate for said microbundle flow, said microbundle leaky bucket asserting microbundle backpressure in accordance with a predetermined microbundle algorithm dependent upon said fill level of said microbundle leaky bucket, wherein said microbundle flow through said port comprises a plurality of threads including a particular thread; an ingress for said particular thread; and a thread leaky bucket for monitoring information packets of said particular thread into said ingress, said thread leaky bucket having a fill level that increases in response to information packets only of said particular thread into said ingress and reduces in accordance with a desired average thread data rate for said particular thread, said thread leaky bucket asserting thread backpressure in accordance with a predetermined thread algorithm dependent upon the fill level of said thread leaky bucket.

20. Apparatus according to claim 19, wherein said port comprises an output port of a switching fabric.

21. Apparatus according to claim 19, comprising a plurality of microbundle leaky buckets including said microbundle leaky bucket, each of said microbundle leaky buckets operable to monitor bandwidth utilization through said port by a respective microbundle, further comprising a distributor operable to, in response to received microbundle leaky bucket draining ticks indicative of overall bandwidth utilization through said port, distribute said ticks among said microbundle leaky buckets, each given one of said microbundle leaky buckets leaking in response to each of said ticks received by the given microbundle leaky bucket, at least if not already at a predetermined minimum fill level.

22. Apparatus according to claim 21, wherein said distributor is operable to distribute said ticks among said microbundle leaky buckets cyclically, skipping over any of said microbundle leaky buckets that are already at a respective predetermined minimum fill level.

23. Apparatus according to claim 19, wherein said information flow through said port flows toward said port via a channel having an ingress, said channel including at least one queue, wherein said microbundle leaky bucket fill level increases in response to information packets in said flow as observed at said ingress.

24. Apparatus according to claim 19, wherein said information flow through said port flows toward said port via a channel having an ingress, said channel being distributed across a plurality of intermediate stage modules, wherein said microbundle leaky bucket fill level increases in response to information packets in said flow as observed at said ingress.

25. Apparatus according to claim 19, comprising a plurality of thread leaky buckets including said thread leaky bucket, each of said thread leaky buckets operable to monitor bandwidth utilization through said port by a respective thread, further comprising a distributor operable to, in response to received thread leaky bucket draining ticks indicative of overall bandwidth utilization through said port, distribute said ticks among said thread leaky buckets, each given one of said thread leaky buckets leaking in response to each of said ticks received by the given thread leaky bucket, at least if not already at a predetermined minimum fill level.

26. Apparatus according to claim 25, wherein said distributor is operable to distribute said ticks among said thread leaky buckets cyclically, skipping over any of said thread leaky buckets that are already at a respective predetermined minimum fill level.

27. Apparatus according to claim 19, wherein said information flow through said port flows toward said port via a channel having an ingress, said channel including at least one queue, wherein said thread leaky bucket fill level increases in response to information packets in said flow as observed at said ingress.

28. Apparatus according to claim 19, wherein said information flow through said port flows toward said port via a channel having an ingress, said channel being distributed across a plurality of intermediate stage modules, wherein said thread leaky bucket fill level increases in response to information packets in said flow as observed at said ingress.

29. Switching fabric apparatus comprising: a plurality of input ports; an output port; data paths for carrying a plurality of information flows from said input ports downstream to said output port, said data paths operate to carry flows from more than one input port to said output port; scheduling apparatus for selecting next packets for transmission through said output port from among said information flows; feed-forward apparatus that operates to send bandwidth utilization signals downstream indicating numbers of blocks of each of said information flows scheduled for downstream transmission, as seen at points upstream of said scheduling apparatus; and a leaky bucket, located downstream of said feed-forward apparatus, for monitoring information flow through said output port, said leaky bucket having a fill level that increases in response to said bandwidth utilization signals.

30. Apparatus according to claim 29, further comprising: distribution apparatus operable to distribute packets of a first one of said information flows among said data paths, wherein said feed-forward apparatus is operable to send bandwidth utilization signals indicating bandwidth utilization of said first information flow, as seen at a point that is no farther downstream than said distribution apparatus.

31. Apparatus according to claim 30, wherein at least one of said data paths includes an information storage queue between said distribution unit and said output port.

32. Apparatus according to claim 29, wherein at least one of said data paths includes an information storage queue, and wherein said feed-forward apparatus is operable to send bandwidth utilization signals indicating bandwidth utilization of one of said information flows, as seen at a point that is upstream of said information storage queue.

33. Apparatus according to claim 29 comprising a plurality of output ports including said output port, wherein: said data paths are for carrying a plurality of information flows from said input ports to said output ports, said data paths being capable of carrying flows from more than one input port to each of said output ports; said scheduling apparatus is for selecting next packets for transmission through each given one of said output ports from among the information flows destined for the given output port; said feed-forward apparatus is operable to send bandwidth utilization signals indicating bandwidth utilization of each of said information flows, as seen at points upstream of said scheduling apparatus; and said leaky bucket is for monitoring information flow through each of said output ports, said leaky buckets having fill levels that increase in response to said bandwidth utilization signals.

34. Apparatus according to claim 33, further comprising: distribution apparatus operable to distribute packets of a first one of said information flows among said data paths, wherein said feed-forward apparatus is operable to send bandwidth utilization signals indicating bandwidth utilization of said first information flow, as seen at a point that is no farther downstream than said distribution apparatus.

35. Apparatus according to claim 34, wherein at least one of said data paths includes an information storage queue between said distribution unit and said output port.

36. Apparatus according to claim 33, wherein at least one of said data paths includes an information storage queue, and wherein said feed-forward apparatus is operable to send bandwidth utilization signals indicating bandwidth utilization of one of said information flows, as seen at a point that is upstream of said information storage queue.

37. Switching apparatus having a plurality of fabric input ports and a fabric output port, and that operates to transport information threads from respective ones of said fabric input ports to said fabric output port, a plurality of subsets of said threads being merged into respective microbundles at respective microbundle ingresses for transmission as respective microbundle flows toward said fabric output port, comprising: an output port scheduler that operates to schedule information packets from said microbundles for transmission through said fabric output port; a microbundle scheduler corresponding to each of said microbundles, each given one of said microbundle schedulers that operates to schedule information packets from the threads of the given microbundle for transmission into the given microbundle; a microbundle leaky bucket corresponding to each of said microbundles, each given one of said microbundle leaky buckets operates to fill in conjunction with the scheduling of information packets for transmission into the corresponding microbundle, and when leaking to leak at a respective leak rate for the corresponding microbundle; and a thread leaky bucket corresponding to each of said threads, each given one of said thread leaky buckets operates to fill in conjunction with information packets of the corresponding thread arriving from a fabric input port corresponding to the given thread, and when leaking to leak at a respective leak rate for the corresponding thread, said switching apparatus operates in response to each particular one of said microbundle leaky buckets filling to a respective high water mark, to stop the transmission of information packets into the particular microbundle and to stop the thread leaky buckets corresponding to the threads of the particular microbundle from leaking, and said switching apparatus further operates in response to each particular one of said thread leaky buckets filling to a respective high water mark, to assert backpressure upstream for the fabric input port corresponding to the thread for the particular thread leaky bucket.

38. Apparatus according to claim 37, wherein said switching apparatus is further operable, in response to backpressure asserted to said fabric output port, to stop the transmission of information packets through said fabric output port and to stop said microbundle leaky buckets from leaking.

39. A method for operating a plurality of leaky buckets, comprising the steps of: receiving a sequence of bucket draining ticks; distributing said ticks cyclically among said leaky buckets, each given one of said leaky buckets leaking in response to each of said ticks received by the given leaky bucket, at least if not already at a predetermined minimum fill level; and draining an antifluid leaky bucket at a steady draining rate unless the fill level of said antifluid leaky bucket falls below a minimum fill level, wherein said step of receiving a sequence of bucket draining ticks comprises the step of receiving said ticks at a rate dependent upon the draining rate of said antifluid leaky bucket.

40. A method according to claim 39, wherein said step of distributing said ticks cyclically comprises the step of distributing said ticks in accordance with a weighted round robin algorithm.

41. A method according to claim 39, wherein each given one of said leaky buckets leaks in response to each of said ticks received by the given leaky bucket, unless the given leaky bucket is already at a predetermined minimum fill level.

42. A method according to claim 39, wherein said step of receiving a sequence of bucket draining ticks comprises the step of receiving said sequence at a steady rate over a particular period of time encompassing a plurality of said ticks.

43. A method according to claim 42, for use with a plurality of information flows all destined for a common port, each of said leaky buckets corresponding to a respective one of said information flows, further comprising the step of filling each given leaky bucket in conjunction with the transmission of information packets into the information flow corresponding to the given leaky bucket.

44. A method according to claim 39, for use with a plurality of information flows all destined for a common port, each of said leaky buckets corresponding to a respective one of said information flows, for use further with an information packet queue for said common port, further comprising the steps of: filling each given leaky bucket in conjunction with the enqueuing of information packets of the flow corresponding to said leaky bucket into said queue; and filling said antifluid leaky bucket in conjunction with the dequeuing of information packets toward said port from said queue.

45. A method according to claim 44, wherein said common port comprises a microbundle ingress.

46. A method according to claim 39, for use with a plurality of information flows all destined for a common port, each of said leaky buckets corresponding to a respective one of said information flows, for use further with an information packet queue for said common port, further comprising the step of filling each given leaky bucket in conjunction with the enqueuing of information packets of the flow corresponding to said leaky bucket into said queue.

47. A multi-stage switch fabric comprising: an input stage having a plurality of input modules; an intermediate stage connected to the input stage and having a plurality of intermediate modules; and an output stage connected to the intermediate stage and having a plurality of output modules, each output module has one or more output ports, wherein the multi-stage switch fabric has: one or more per-microbundle monitors, each that monitors a microbundle flow of a corresponding output port and assert microbundle backpressure signals for the microbundle flow, each microbundle flow having a plurality of threads; and one or more per-thread monitors, each to that monitors a different thread and assert thread backpressure signals for the thread, wherein each per-thread monitor is implemented in the input stage.

48. The multi-stage switch fabric of claim 47, wherein each per-microbundle monitor is implemented outside of the output stage.

49. The multi-stage switch fabric of claim 48, wherein each per-microbundle monitor is implemented in the intermediate stage.

50. The multi-stage switch fabric of claim 47, wherein each per-thread monitor has a feed-forward counter that sends bandwidth utilization signals downstream to a corresponding per-microbundle monitor indicating numbers of blocks of each corresponding thread scheduled for downstream transmission as seen at a point upstream of the corresponding output port.

51. The multi-stage switch fabric of claim 50, wherein each per-microbundle monitor maintains one or more microbundle leaky buckets, wherein a fill level of a microbundle leaky bucket is adjusted based on the bandwidth utilization signals received from the feed-forward counter.

52. The multi-stage switch fabric of claim 51, wherein the fill level of the microbundle leaky bucket is further adjusted based on a desired average microbundle data rate for the corresponding microbundle flow.

53. A multi-stage switch fabric comprising: an input stage having a plurality of input modules; an intermediate stage connected to the input stage and having a plurality of intermediate modules; an output stage connected to the intermediate stage and having a plurality of output modules, each output module has one or more output ports, wherein the multi-stage switch fabric has: one or more microbundle leaky buckets, each that monitors a microbundle flow of a corresponding output port, each microbundle flow having a plurality of threads; and one or more thread leaky buckets, each that monitors a different thread; and a feed-forward counter that sends bandwidth utilization signals downstream to a corresponding microbundle leaky bucket indicating numbers of blocks of the corresponding thread scheduled for downstream transmission as seen at a point upstream of the corresponding output port.

54. The multi-stage switch fabric of claim 53, wherein a fill level of the corresponding microbundle leaky bucket is adjusted based on the bandwidth utilization signals received from the feed-forward counter.

55. The multi-stage switch fabric of claim 54, wherein the fill level of the microbundle leaky bucket is further adjusted based on a desired average microbundle data rate for the corresponding microbundle flow.

56. A multi-stage switch fabric comprising: an input stage having a plurality of input modules; an intermediate stage connected to the input stage and having a plurality of intermediate modules; and an output stage connected to the intermediate stage and having a plurality of output modules, each output module has one or more output ports, wherein: the multi-stage switch fabric has: one or more per-microbundle monitors, each that monitors a microbundle flow of a corresponding output port and assert microbundle backpressure signals for the microbundle flow, each microbundle flow having a plurality of threads; and one or more per-thread monitors, each that monitors a different thread and assert thread backpressure signals for the thread; and each per-thread monitor has a feed-forward counter that sends bandwidth utilization signals downstream to a corresponding per-microbundle monitor indicating numbers of blocks of each corresponding thread scheduled for downstream transmission as seen at a point upstream of the corresponding output port.

57. The multi-stage switch fabric of claim 56, wherein each per-microbundle monitor maintains one or more microbundle leaky buckets, wherein a fill level of a microbundle leaky bucket is adjusted based on the bandwidth utilization signals received from the feed-forward counter.

58. The multi-stage switch fabric of claim 57, wherein the fill level of the microbundle leaky bucket is further adjusted based on a desired average microbundle data rate for the corresponding microbundle flow.

---

Description

---

BACKGROUND

1. Field of the Invention

The invention relates to switching fabrics, and more particularly to a flow control method and apparatus for fairly allocating the bandwidth capacity of the fabric to multiple input flows.

2. References

The following U.S. patents are incorporated herein by reference: U.S. Pat. Nos. 6,388,992; 5,903,735; 5,280,470; 5,930,234; 5,455,826.

3. Description of Related Art

A switch fabric for a data network is a device that allows data from any of several input ports to be communicated switchably to any of several output ports. Early data networks were based on circuit switching, in which fixed routes were established through the fabric for each session. The peak bandwidth demand of each session was allocated to the route for the entire duration of the session. When session traffic was bursty, however, circuit switching resulted in under-utilization of network resources during the time between bursts. Packet switching was developed to overcome this disadvantage, thus improving the network utilization for bursty traffic.

Packet switched networks dynamically allocate bandwidth according to demand. By segmenting the input flow of information into units called "packets," and processing each packet as a self-contained unit, packet switched networks allow scheduling of network resources on a per-packet basis. This enables multiple sessions to share the fabric resources dynamically by allowing their packets to be interleaved across the fabric. Typically each packet includes a header indicating its destination port, and the fabric includes a routing mechanism for determining a route through the fabric, on a per-packet basis.

Small switching fabrics can be constructed from crossbar switches, in which a scheduler configures the crossbar in a each time slot to connect a set of input ports to set of output ports in a one to one mapping (or one to many in the multicast case). The crossbar scheduler decides what the mapping between inputs and outputs should be in a particular time slot. Both input port constraints and output port constraints are taken into account by the scheduler: input ports contending for the same output port share the bandwidth of that output port in some manner that the crossbar scheduling algorithm considers fair, and output port usage is optimized by attempting to have every output port carry a cell in each time slot for which any input port has a cell destined for that output port.

Crossbar scheduling algorithms are often designed to mimic maximally weighted matching, a discipline that tries to maximize a particular objective function in each time slot by making more of an effort to grant requests from inputs which have longer queues. The strict maximally weighted matching discipline is a very hard problem, though, so crossbar scheduling algorithms have been devised that only approximate maximally weighted matching. In one such crossbar scheduling algorithm, known as ISLIP, inputs keep virtual output queues (VOQs) in which cells bound for different output ports wait at the inputs for transfer. Before each time slot begins, each input submits to a central scheduler or arbiter a request to connect with a certain output. Part of the ISLIP algorithm is a procedure for the input to decide which output to request being connected to, among all of the outputs that the input has cells to send to. The central scheduler collects all of the requests, and chooses which to grant. There can be several rounds of requests and grants so that an input that did not get its first request granted can submit a request for connection to a different output to which it has data to send.

It can be seen that a crossbar scheduler needs to be centralized, both in the sense that it needs to coordinate the functioning of all input ports and in the sense that it needs to coordinate the functioning of all output ports. It needs to coordinate all the input ports because it needs to ensure that no more than one input port is transmitting a cell to the same output port in the same time slot; crossbar fabrics (at least pure ones) cannot tolerate such a situation. It needs to coordinate all output ports in order to maximize utilization of the bandwidth capacity of each one. In short, a crossbar scheduler needs to be aware of the global state of the overall system in each time slot in order to do its job well.

The centralized nature of crossbar schedulers tends to prevent the scaling of crossbar switching fabrics to large numbers of inputs and outputs. At least two factors limit the scalability of crossbar switching fabrics. First, as the number of input and output ports grow, and channel data rates increase, it becomes increasingly difficult to design logic circuitry that is fast enough to make all the required calculations in time for each time slot. Since the crossbar scheduler must be centrally implemented, its complexity usually increases more than linearly with the number of input and output ports that the algorithm is required to handle. Second, as the number of input and output ports grows, per-chip or per-module pin count limitations begin to require the spreading of the fabric over more than one chip or module. In this case it also becomes increasingly difficult to design in sufficient control signal capacity to transmit the requests and grants between the centralized scheduler and all the various inputs.

As the need for larger and larger switching fabrics increases, therefore, it becomes more and more important to find a mechanism for controlling the transmission of data packets from switch inputs to switch outputs, in a manner that scales much more easily to larger fabrics.

SUMMARY OF THE INVENTION

In an aspect of the invention, roughly described, the packet scheduling problem is simplified enormously by removing the requirement that the scheduling algorithm coordinate among all the input ports, and removing the requirement that it consider the constraints of any of the output ports. Instead, the input queues are divided into small groups (each group perhaps located on a different input module), and a separate, independent queue scheduler is provided to serve each group. Each queue scheduler can be ignorant of the decisions being made by other schedulers responsible for serving other input queues, because the problem of more than one uncoordinated input sending a packet to the same output port is handled by including a memory between the inputs and each given output that has enough writing bandwidth to be able to accept packets from all the input port schedulers at the same time. In one embodiment, a multistage switching fabric is used instead of a crossbar fabric. In another embodiment, a single stage switching fabric is used with sufficiently fast internal memory. By removing the requirement that the scheduler responsible for one group of input queues coordinate with the schedulers responsible for all other groups of input queues, the requirement for control signaling among the input ports also can be removed. Thus as the system grows to accommodate more input ports, the packet transmission control mechanism need not increase significantly in complexity. Instead, the function can be divided among more queue schedulers, each no more complex than the basic queue scheduler. And when the system grows to the point of requiring input ports to be distributed among a number of input modules, the packet transmission control function no longer restricts this growth because the queue schedulers, too, can be distributed among the same number of input modules without incurring additional costs for communicating control signaling among the input ports.

Each queue scheduler is also ignorant of the instantaneous state of the output ports; the scheduler makes its decisions based only (with one exception) on the local state of its input queues. Output port control is handled by a separate set of flow monitors and supervisors which police output port bandwidth utilization by each of the individual input threads and assert backpressure toward the input port queue scheduler that is responsible for scheduling packets for any thread that is exceeding its bandwidth allocation. The one exception above with respect to the local nature of the factors on which a queue scheduler makes its decisions, is that the queue scheduling algorithm is modified to the extent that input queues for which backpressure is asserted are ineligible for scheduling. By policing output port usage and controlling bandwidth allocations through backpressure (or other feedback) rather than affirmatively considering all output port states in each scheduling decision, the need for control signaling between the output ports and the schedulers, too, is vastly reduced. In addition, the policing can occur on a much slower time scale than the per-time-slot output port utilization coordination used by conventional crossbar schedulers, thereby reducing the control signaling even further.

Accordingly, the aspects of the invention described above nearly eliminate the centralized scheduler as a bottleneck on the growth of packet-based switching fabrics to accommodate greater numbers of input and output ports.

The use of a multistage fabric for packet-based switching may be counterintuitive because in the past, such fabrics have been used mostly for circuit-based switching applications. In a multistage switching fabric, data transmission from a number of input ports to a number of output ports is accomplished through one or more intermediate stages. Each stage can have one or more module, each implementing its own internal switch. In addition, in a fully connected network, all of the modules in each stage of the network have respective communication paths to all of the modules in the next stage. A basic network of this sort has three stages (input, intermediate and output), but networks with any odd number of stages theoretically can be constructed by replacing the modules in any given stage with smaller multi-stage networks in recursive fashion.

A special case of multi-stage switch networks was studied by Clos in C. Clos, "A Study of Non-Blocking Switching Networks", Bell System Technical Journal, March 1953, vol. 32, No. 3, pp. 406-424, incorporated by reference herein. A so-called Clos network has three stages, any of which can be recursed to create effectively a network with a larger odd number of stages. All input stage modules (sometimes simply called "input modules") of the network have an equal number of input ports, all output stage modules (sometimes simply called "output modules") have an equal number of output ports, and all input and output modules are fully interconnected with all intermediate stage modules (sometimes simply called "intermediate modules"). Clos networks can be symmetric, in which case the number of modules and the number of ports per module on the input side match the corresponding values on the output side, or they can be asymmetric, in which case the number of modules or the number of ports per module on the input side do not necessarily match the corresponding values for the output side. A symmetric Clos network, therefore, can be characterized by a triple (m,n,r) where m is the number of modules in the intermediate stage, n is the number of input ports on each input module (the same as the number of output ports on each output module), and r is the number of modules in the input stage (the same as the number of modules in the output stage). An asymmetric Clos network must be characterized by a quintuple (m, n.sub.i, r.sub.i, n.sub.o, r.sub.o).

Multistage topologies naturally lend themselves to distributed implementations, but until now it was not apparent how such a fabric could be adapted for use in a packet-based switch. It is much easier to control dataflow through such a switch in a circuit switched environment (where routing changes occur on the order of seconds, minutes, hours or longer) than in a packet switched environment (where routing changes occur on the order of milliseconds or microseconds or shorter). In particular, any attempt to use known crossbar scheduling algorithms to control the packet data transmission across a multistage fabric would quickly stifle scalability for the reasons mentioned above. As described above, aspects of the invention overcome that problem.

As mentioned above, in an aspect of the invention, a data packet transmission across the switching fabric preferably is controlled by a modified queue scheduling algorithm. A queue scheduling algorithm attempts to allocate a resource fairly among a number of input queues contending for that resource. In the typical case of a router, the resource is an output port of the router. In the present case the resource is the switching bandwidth capacity of a multistage switch. Queue scheduling algorithms differ from crossbar scheduling algorithms in that whereas crossbar scheduling algorithms choose an input port to be connected to each output port in each time slot, queue scheduling algorithms (as used in a multistage switching fabric) choose among non-empty input queues for transmission into the next stage of the fabric. A queue scheduling algorithm need consider only the state of the input queues that it controls, not the state of any fabric output port be serviced in each time slot. The output port state is taken into account only by modifying the queue scheduling algorithm to render backpressured input queues ineligible for scheduling.

As with crossbar scheduling algorithms, a number of different kinds of queue scheduling algorithms have been developed. In one algorithm, known as FIFO (first-in-first-out), packets are allocated access to the shared resource in the same order in which they are received. In another, known as priority queuing (PQ), incoming data packets are first classified into one of a number of predefined classes, and then placed in a queue specific to that class. The classes have a predefined priority order, and the queuing algorithm schedules packets from the head of one queue only when all higher-priority queues are empty. Yet another algorithm, known as fair queuing (FQ), incoming packets are placed in class-specific queues as in the priority queuing algorithm, but then the queues are serviced in round-robin order. A refinement on FQ, known as weighted fair queuing (WFQ), accommodates variable-length packets and assignment of different percentages of the bandwidth capacity of the shared resource to different ones of the input queues. In yet another algorithm, known as weighted round robin (WRR) queuing, or class-based queuing (CBQ), each class is pre-assigned a percentage of the bandwidth capacity of the shared resource. Incoming packets are placed in class-specific queues and serviced in round-robin order, except that queues that were assigned a larger percentage of the bandwidth are allowed to send a greater number of packets in each round. But since WRR does not allocate bandwidth as desired when the packet size is variable, yet another algorithm, Deficit Round Robin (DRR) queuing has been developed. According to the DRR algorithm, a deficit count is maintained for each input queue. Before packets are scheduled from a current input queue, a quantum is added to the deficit count for that queue. If the input queues are assigned different bandwidths, then the quantum for each input queue can be proportional to the relative bandwidth assigned to that queue (Deficit Weighted Round Robin--DWRR). Then, if the length of the packet is smaller than the deficit count for the input queue, the packet is selected from the current input queue and the deficit counter for that input queue is reduced by the length of the packet. The scheduler continues selecting packets from the same input queue, concomitantly reducing the deficit count for that queue, until the length of the next packet at the head of the queue is greater than the deficit count for the current queue. The scheduler then moves on to the next input queue in round robin sequence, adds the quantum to the deficit count for the new queue, and tests the count against the length of the new packet. Many other queue scheduling algorithms exist as well, including variations on those mentioned above. Any can be used in an embodiment of the invention, with the modification that backpressured input queues are ineligible.

Accordingly, roughly described, in an aspect of the invention, a switching fabric manages per-flow bandwidth utilization of the output port bandwidth capacity through the use of a reactive policing mechanism, rather than a proactive scheduling mechanism, of the flows destined for the output port. In another aspect, the fabric includes many supervisors distributed across the fabric, rather than a single centralized scheduler. In another aspect, as described more fully hereinafter, the switching fabric is able to guarantee bandwidth capacity at a significantly finer granularity of data flows than has been feasible previously, and is also able to allocate unused bandwidth among needy flows with strict or nearly strict fairness. of In another aspect, a switching fabric uses leaky buckets to apply backpressure in response to overutilization of downstream port capacity by particular subflows. In another aspect, a switching fabric includes a cascaded backpressure scheme, in which individual flows from input modules to a given fabric output port are backpressured as a group in response to overutilization of the fabric output port by the individual flow, and individual subflows feeding a given one of such flows are backpressured individually in response to overutilization of the given flow bandwidth capacity by the individual subflow. Many other features and aspects are set forth herein and in the appended claims.

BRIEF DESCRIPTION OF THE DRAWINGS

The invention will be described with respect to specific embodiments thereof, and reference will be made to the drawings, in which:

FIGS. 1, 1A, 1B, 1C, 1D, 2 and 3 are block diagrams of modular switch fabrics incorporating features of the invention.

FIG. 4 is a functional block diagram of pertinent components of one of the input modules in FIG. 1.

FIG. 5 is a functional block diagram of pertinent components of one of the intermediate stage modules in FIG. 1.

FIG. 6 is a functional block diagram of pertinent components of one of the output modules in FIG. 1.

FIG. 7 is a functional block diagram of a simplified switching fabric.

FIG. 8 is a functional block diagram of a per-microbundle monitor in an intermediate stage module.

FIG. 9 is a functional block diagram of certain components of an input module.

FIG. 10 is an algorithm drawing illustrating the draining hierarchy in a single-stage embodiment.

FIG. 11 sets forth a process for filling output-class pair leaky buckets.

FIG. 12 is a flow chart illustrating the logic of an across-class scheduler.

FIG. 13 is a flow chart illustrating which operations of the draining algorithm occur in which epoch.

FIG. 14 is a flow chart illustrating the logic of the within-class allocation.

FIG. 15 shows varying backpressure assertion thresholds for a multistage topology.

FIG. 16 shows the thresholds of FIG. 15 broken down by stages, type of leaky bucket, and device base memory management.

DETAILED DESCRIPTION

FIG. 1 is a block diagram of a modular switch fabric 100 incorporating the invention. The fabric of FIG. 1 has three stages: an input stage 110, an intermediate stage 112 and an output stage 114. The stages are also sometimes referred to herein as the first, second and third stage, respectively. Any or all of the modules can implement its switching function internally by using a crossbar switch, one or more recursive levels of 3-stage sub-networks, or by any other structure. The input stage 110 of the fabric has r input modules 116, numbered (1,1) through (1,r). Each input module 116 has n input ports and mp output ports. The intermediate stage 112 has m modules 118, numbered (2,1) through (2,m). The number of data links from each input module 116 to each intermediate stage module 118 is p. Alternatively, a different embodiment can implement only one data link from each input module 116 to each intermediate stage module 118, but with a capacity of p times the capacity of each fabric input port. Each intermediate stage module 118 includes rp input ports and rp output ports. The output stage 114 of the fabric has r output modules 120, numbered (3,1) through (3,r). Each output module 120 has mp input ports and n output ports. Not shown in FIG. 1 are input line cards, which are upstream of the input stage 110, and output line cards, which are downstream of output stage 114. Also not shown are serializer/deserializer integrated circuits used for transporting signals across a switch backplane.

The fabric of FIG. 1 is an (m,n,r) symmetrical Clos network, but the general principles of the invention will also work with asymmetrical Clos networks, networks which are not fully interconnected, networks in which not all of the input modules have an equal number of input ports and/or not all output modules have an equal number of output ports, and so on. Clos networks are preferred, however, because their throughput properties are easier to analyze and prove theoretically. Clos networks are preferred also because they are easier to build in a modular fashion. In particular, all of the modules 116 in the input stage 110 of the fabric of FIG. 1 are identical; all of the modules 118 in the intermediate stage 112 of the fabric of FIG. 1 are identical; and all of the modules 120 in the output stage 114 of the fabric of FIG. 1 are identical. Preferably, in fact, all of the modules in all of the stages of the fabric of FIG. 1 are fabricated from identical integrated circuit chips, sometimes referred to herein as Cashmere chips, which are designed to include all of the features required for any stage of the fabric. The chip is configured as an input module 116, an intermediate stage module 118 or an output module 120, by pin strapping or programming, depending on the stage at which the particular chip is deployed in the fabric.

Because of the modular nature of the architecture, non-blocking fabrics with various numbers of input and output ports and various topologies can be built with Cashmere integrated circuit chips. Using a companion Pashmina integrated circuit chip, several such fabrics can be connected in parallel to build fabrics with a number of quad-speed input and output ports and 1:n redundancy. Blocking arch