Striping algorithm for switching fabric

• US 7,586,909 B1
• Filed: 10/11/2002
• Issued: 09/08/2009
• Est. Priority Date: 03/06/2002
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Agere Systems Incorporated (Broadcom, Inc.)
• Inventors: Myers, Roy T., Chin, Chung Kuang, Walrand, Jean, Musacchio, John T.
• Primary Examiner(s): HO, DUC CHI
• Application Number:
  US10/269,928
• Time in Patent Office: 2,524 Days
• Field of Search: None
• US Class Current: 370/388
• CPC Class Codes: H04L 49/1515 Non-blocking multistage, e.g. Clos
• CPC Class Codes: H04L 49/201 Multicast operation; Broadcast operation
• CPC Class Codes: H04L 49/205 Quality of Service based
• CPC Class Codes: H04L 49/25 Routing or path finding in a switch fabric
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 49/3018 Input queuing
• CPC Class Codes: H04L 49/3027 Output queuing
• CPC Class Codes: H04L 49/3072 Packet splitting
• CPC Class Codes: H04Q 3/68 Grouping or interlacing selector groups or stages

Abstract

A striping algorithm selects a route on which to transmit each next data segment, in dependence upon relative channel loading so far, taking account of multicast. Input modules can keep a channel loading history for each route it has, and can update its history for each route that a data segment follows through the fabric. In an embodiment, the input module transmits each data segment toward an i'"'"'th intermediate stage module, where i minimizes
q(i,a(G),c)+q(i,b(G),c)+ . . . +q(i,k(G),c),
where q(i, j, c) indicates the number of bytes of data sent, during a given prior time period, from the input module to each j'"'"'th one of the output modules via each i'"'"'th one of the intermediate stage modules, and a(G), b(G), . . . , and k(G) are the output module(s) in the multicast group G to which the data segment is destined.

Claims

1. A method for routing segments of data belonging to a class of a set of one or more classes, from a first input module in an input stage to a plurality of output modules in an output stage, via a plurality of intermediate stage modules, said first input module having a data path to each of said intermediate stage modules and each of said intermediate stage modules having a data path to at least one of said output modules, an intermediate stage module including a multicast replicator for forwarding a data segment received from an input module to more than one of said output modules, the method comprising the steps of said first input module:

(a) determining, in dependence upon a measure of relative channel loading of routes from said first input module to said output stage via said data paths, due to data of said class that originated from said first input module during a given prior time period, a given intermediate stage module of said intermediate stage modules through which to send a given next data segment of said class to be sent by said first input module; and

(b) sending said given next data segment on the data path to said given intermediate stage module, wherein;

the data originating from said first input module during said given prior time period includes a prior data segment of said class replicated by said multicast replicator for forwarding to more than one of said output modules, and

the channel loading due to said prior data segment is reflected in said measure of relative channel loading of each of the routes taken by said prior data segment from said first input module to modules in said output stage.

2. A method according to claim 1, wherein said class is a class of service.

3. A method according to claim 1, further comprising an additional method for routing segments of data not belonging to said class.

4. A method according to claim 1, further for routing segments of data belonging to said class from a second input module to said output stage, via said plurality of intermediate stage modules, said second input module having a data path to each of said intermediate stage modules, further comprising the step of said second input module:

in dependence upon the measure of relative channel loading of routes from said second input module to said output stage via said data paths due to data of said class that originated from said second input module during a particular prior time period, and regardless of the measure of relative channel loading of the routes from said first input module to an output module due to data of said class that originated from said first input module during said particular prior time period, determining a particular one of said intermediate stage module through which to route a particular next data segment of said class to be sent by said second input module; and

sending said particular next data segment to said particular intermediate stage module.

5. A method according to claim 1, wherein the measure of relative channel loading of a particular route is given by the relative number of data segments sent along the particular route.

6. A method according to claim 1, wherein the measure of relative channel loading of a particular route is given by the relative number of bytes of data of said class, originating from said first input module, that were sent along the particular route.

7. A method according to claim 1, wherein each of said routes from said first input module to said output stage has a respective channel capacity,

and wherein the measure of channel loading of said routes is normalized for said respective channel capacities.

8. A method according to claim 1, further comprising the step of maintaining counts indicating at least the relative number of bytes of data of said class, originating from said first input module, that were sent along each of said routes from said first input module to said output stage during said given prior time period,

and wherein said step of determining a given intermediate stage module through which to send a given next data segment comprises the step of determining said given intermediate stage module in dependence upon said counts.

9. A method according to claim 8, wherein said step of maintaining counts comprises the step of updating said counts in conjunction with each data segment of said class, originating from said first input module, that was sent along each of said routes from said first input module to said output stage during said given prior time period.

10. A method according to claim 8, wherein said step of maintaining counts comprises the step of updating said counts in conjunction with transmission of said prior data segment from said first input module, to reflect channel loading of each of the routes taken by said prior data segment to modules in said output stage.

11. A method according to claim 1, wherein said given prior time period is an immediately prior time period.

12. A method according to claim 1, wherein said step of determining a given intermediate stage module comprises the step of determining said given intermediate stage module in dependence upon the measure of relative channel loading of only the routes from said first input module to each output module to which said given next data segment is destined.

13. A method according to claim 12, wherein said given next data segment is destined for each of a plurality of said output modules.

14. A method according to claim 1, wherein said first input module has a plurality of data links to one of said intermediate stage modules, each of said data links defining a separate route.

15. A method according to claim 1, wherein said first input module has a plurality of data links to one of said intermediate stage modules, all of said data links being part of a single route.

16. A method according to claim 1, wherein one of said intermediate stage modules comprises a plurality of input sub-modules in an input sub-stage, a plurality of output sub-modules in an output sub-stage, and a plurality of intermediate sub-modules in an intermediate sub-stage, each of the input sub-modules having a data path to each of said intermediate sub-modules and each of said intermediate sub-modules having a data path to each of said output sub-modules.

17. A method according to claim 1, wherein said step of determining a given intermediate stage module of said intermediate stage modules comprises the step of selecting an i'"'"'th one of said intermediate stage modules, where i minimizes

q(i,j=a(G),c)+q(i,j=b(G),c)+ . . . +q(i,j=k(G),c),

where:

q(i, j, c) indicates the number of bytes of data of said class sent, during said given prior time period, from said first input module to each j'"'"'th one of said output modules via each i'"'"'th one of said intermediate stage modules, normalized by a respective channel capacity from said first input module to each j'"'"'th one of said output modules via each i'"'"'th one of said intermediate stage modules,

G is a multicast group of at least one output module to which the given next data segment is destined,

a(G), b(G), . . . , and k(G) are the output module(s) in multicast group G, and c is the class of the given next data segment.

18. A method according to claim 17, further comprising, in conjunction with the sending of a particular data segment of a class cc from said first input module to the output ports in a multicast group GG of more than one output port, via an ii'"'"'th one of said intermediate stage modules,

the step of increasing the number of bytes of data indicated by each of q(ii, jj=a(GG), cc), q(ii, jj=b(GG), cc), . . . , and q(ii, jj=k(GG), cc), relative to all other q(ii, jj, cc), by the number of bytes in the given next data segment, normalized by the respective channel capacity from said first input module to each j'"'"'th one of said output modules via each i'"'"'th one of said intermediate stage modules,

where a(GG), b(GG), . . . , and k(GG) are the output ports in multicast group GG.

19. A method according to claim 17, further comprising, in conjunction with the sending of a particular data segment of a class cc from said first input module to the output ports in a multicast group GG of more than one output port, via an ii'"'"'th one of said intermediate stage modules,

the step of increasing the number of bytes of data indicated by each of q(ii, jj=a(GG), cc), q(ii, jj=b(GG), cc), . . . , and q(ii, jj=k(GG), cc), relative to all other q(ii, jj, cc), by the number of bytes in the given next data segment times respectively L_max/L(ii, jj=a(GG)), L_max/L(ii, jj=b(GG)), . . . , L_max/L(ii, jj=k(GG)),

where a(GG), b(GG), . . . , and k(GG) are the output ports in multicast group GG,

where L(i,j) is a data rate from said first input module, via intermediate module i, to output module j,

and where L_max is the maximum of all the L(i,j).

20. A method according to claim 19, wherein L(ii, jj=a(GG)), L(ii, jj=b(GG)), . . . , and L(ii, jj=k(GG)) are all equal to L_max, and wherein the step of increasing the number of bytes of data indicated by each of q(ii, jj=a(GG), cc), q(ii, jj=b(GG), cc), . . . , and q(ii, jj=k(GG), cc), relative to all other q(ii, jj, cc), by the number of bytes in the given next data segment.

21. A method according to claim 1, wherein said step of determining a given intermediate stage module of said intermediate stage modules comprises the step of selecting an i'"'"'th one of said intermediate stage modules, where i minimizes

q(i,j=a(G),c)/L(i,j=a(G))+q(i,j=b(G),c)/L(i,j=b(G))+ . . . +q(i,j=k(G),c)/L(i,j=k(G)),

where:

q(i, j, c) indicates the number of bytes of data of said class sent, during said given prior time period, from said first input module to each j'"'"'th one of said output modules via each i'"'"'th one of said intermediate stage modules,

L(i, j) indicates a data rate from said first input module to each j'"'"'th one of said output modules via each i'"'"'th one of said intermediate stage modules,

G is a multicast group of at least one output module to which the given next data segment is destined,

a(G), b(G), . . . , and k(G) are the output module(s) in multicast group G, and c is the class of the given next data segment.

22. A method according to claim 1, wherein said first input module is disposed on a single integrated circuit chip with one of said output modules.

23. An input module for use in a switch fabric that contains an input stage including said input module, plurality of output modules in an output stage, and a plurality of intermediate stage modules, said input module having a data path to each of said intermediate stage modules and each of said intermediate stage modules having a data path to at least one of said output modules, at least one of said intermediate stage modules including a multicast replicator for forwarding a data segment received from an input module to more than one of said output modules, for routing segments of data belonging to a class of a set of one or more classes from said input module to said output modules via said intermediate stage modules, the input module comprising:

determining logic that, in dependence upon a measure of relative channel loading of routes from said input module to said output stage via said data paths, due to data of said class that originated from said input module during a given prior time period, determines a given intermediate stage module of said intermediate stage modules through which to send a given next data segment of said class to be sent by said input module; and

sending logic that sends said given next data segment on the data path to said given intermediate stage module, wherein for a prior data segment sent by said sending logic and destined for more than one of said output modules, the channel loading due to said prior data segment is reflected in said measure of relative channel loading of each of the routes taken by said prior data segment from said input module to modules in said output stage.

24. An input module according to claim 23, wherein said class is a class of service.

25. An input module according to claim 23, further comprising additional logic for routing segments of data not belonging to said class.

26. An input module according to claim 23, wherein said input stage further includes a second input module having a data path to each of said intermediate stage modules.

27. An input module according to claim 23, wherein the measure of relative channel loading of a particular route is given by the relative number of data segments for which the intermediate stage module of the particular route was determined by said determining logic.

28. An input module according to claim 23, wherein the measure of relative channel loading of a particular route is given by the relative number of bytes for which the intermediate stage module of the particular route was determined by said determining logic.

29. An input module according to claim 23, wherein each of said routes from said input module to said output stage has a respective channel capacity,

and wherein the measure of channel loading of said routes is normalized for said respective channel capacities.

30. An input module according to claim 23, further comprising history logic which maintains counts indicating at least the relative number of bytes of data of said class, originating from said input module, that were sent along each of said routes from said input module to said output stage during said given prior time period,

and wherein said determining logic determines said given intermediate stage module in dependence upon said counts.

31. An input module according to claim 30, wherein said history logic updates said counts in conjunction with each data segment of said class, originating from said input module, for which a route was determined by said determining logic during said given prior time period.

32. An input module according to claim 30, wherein said history logic updates said counts in conjunction with each prior data segment of said class, originating from said input module and destined for more than one of said output modules, to reflect channel loading of each of the routes taken by said prior data segment to modules in said output stage.

33. An input module according to claim 23, wherein said given prior time period is an immediately prior time period.

34. An input module according to claim 23, wherein said determining logic determines said given intermediate stage module in dependence upon the measure of relative channel loading of only the routes from said input module to each output module to which said given next data segment is destined.

35. An input module according to claim 23, wherein said determining logic comprises logic which selects an i'"'"'th one of said intermediate stage modules, where i minimizes

q(i,j=a(G),c)+q(i,j=b(G),c)+ . . . +q(i,j=k(G),c),

where:

q(i, j, c) indicates the number of bytes of data of said class sent, during said given prior time period, from said input module to each j'"'"'th one of said output modules via each i'"'"'th one of said intermediate stage modules, normalized by a respective channel capacity from said input module to each j'"'"'th one of said output modules via each i'"'"'th one of said intermediate stage modules,

G is a multicast group of at least one output module to which the given next data segment is destined,

a(G), b(G), . . . , and k(G) are the output module(s) in multicast group G, and

c is the class of the given next data segment.

36. An input module according to claim 35, further comprising history logic which, in conjunction with the sending of a particular data segment of a class cc from said input module to the output ports in a multicast group GG of more than one output port, via an ii'"'"'th one of said intermediate stage modules,

increases the number of bytes of data indicated by each of q(ii, jj=a(GG), cc), q(ii, jj=b(GG), cc), . . . , and q(ii, jj=k(GG), cc), relative to all other q(ii, jj, cc), by the number of bytes in the given next data segment, normalized by the respective channel capacity from said input module to each j'"'"'th one of said output modules via each i'"'"'th one of said intermediate stage modules,

where a(GG), b(GG), . . . , and k(GG) are the output ports in multicast group GG.

37. An input module according to claim 35, further comprising history logic which, in conjunction with the sending of a particular data segment of a class cc from said input module to the output ports in a multicast group GG of more than one output port, via an ii'"'"'th one of said intermediate stage modules,

increases the number of bytes of data indicated by each of q(ii, jj=a(GG), cc), q(ii, jj=b(GG), cc), . . . , and q(ii, jj=k(GG), cc), relative to all other q(ii, jj, cc), by the number of bytes in the given next data segment times respectively L_max/L(ii, jj=a(GG)), L_max/L(ii, jj=b(GG)), . . . , L_max/L(ii, jj=k(GG)),

where a(GG), b(GG), . . . , and k(GG) are the output ports in multicast group GG,

where L(i,j) is a data rate from said input module, via intermediate module i, to output module j,

and where L_max is the maximum of all the L(i,j).

38. An input module according to claim 23, wherein said determining logic comprises logic which selects an i'"'"'th one of said intermediate stage modules, where i minimizes

q(i,j=a(G),c)/L(i,j=a(G))+q(i,j=b(G),c)/L(i,j=b(G))+ . . . +q(i,j=k(G),c)/L(i,j=k(G)),

where:

q(i, j, c) indicates the number of bytes of data of said class sent, during said given prior time period, from said input module to each j'"'"'th one of said output modules via each i'"'"'th one of said intermediate stage modules,

L(i, j) indicates a data rate from said input module to each j'"'"'th one of said output modules via each i'"'"'th one of said intermediate stage modules,

G is a multicast group of at least one output module to which the given next data segment is destined,

a(G), b(G), . . . , and k(G) are the output module(s) in multicast group G, and

c is the class of the given next data segment.

39. An input module according to claim 23, comprising an integrated circuit chip on which is disposed both said input module and one of said output modules.

40. A data switch including an input module according to claim 23.

41. A method for routing segments of data belonging to a class of a set of one or more classes, from a first input module to a plurality of output modules via a plurality of intermediate stage modules in accordance with a striping algorithm, said first input module having a data path to each of said intermediate stage modules and each of said intermediate stage modules having a data path to each of said output modules, an intermediate stage module including a multicast replicator for outputting a data segment received from an input module to more than one of said output modules, the method in accordance with the striping algorithm comprising the step of said first input module sending each subject data segment of a plurality of subject data segments via intermediate stage module i, where i minimizes

q(i,j=a(G),c)+q(i,j=b(G),c)+ . . . +q(i,j=k(G),c),

where:

q(i, j, c) indicates the number of bytes of data of each class c sent, during a particular prior time period, from said first input module to each j'"'"'th one of said output modules via each i'"'"'th one of said intermediate stage modules,

G is a multicast group of at least one output module to which the subject data segment is destined,

a(G), b(G), . . . , and k(G) are the output module(s) in multicast group G, and

c is the class of the subject data segment,

and wherein the data sent from said first input module during said particular prior time period includes at least one data segment replicated by said multicast replicator for output to more than one of said output modules.

42. A method according to claim 41, wherein all of said data segments are data blocks of constant length.

43. A method according to claim 41, wherein not all data segments of class c sent during said particular prior time period from said first stage module to output module a(G) are of constant length.

44. A method according to claim 41, wherein one of said subject data segments is destined for more than one of said output modules.

45. A method according to claim 41, wherein each of said intermediate stage modules includes a multicast replicator for outputting data segments received from said first input module to more than one output module in said plurality of output modules.

46. A method according to claim 41, for use in routing segments of data from a plurality of input modules to said plurality of output modules via said plurality of intermediate stage modules, said plurality of input modules including said first input module, and each input module in said plurality of input modules having a data path to each of said intermediate stage modules.

47. A method according to claim 46, wherein each input module in said plurality of input modules is disposed on a single integrated circuit chip with a respective one of said output modules.

48. A method according to claim 41, further for routing segments of data belonging to a class in said set of one or more classes, from a second input module to said plurality of output modules via said plurality of intermediate stage modules, said second input module having a data path to each of said intermediate stage modules, comprising the step of said second input module sending each given data segment via intermediate stage module i₂, where i₂ minimizes

q₂(i₂,j₂=a(G₂),c₂)+q₂(i₂,j₂=b(G₂),c₂)+ . . . +q₂(i₂,j₂=k(G₂),c₂);

where;

q₂(i₂, j₂, c₂) indicates the number of bytes of data of each class c₂ sent, during a given prior time period, from said second input module to each j₂'"'"'th one of said output modules via each i₂'"'"'th one of said intermediate stage modules,

G₂ is a multicast group of at least one output module to which the given data segment is destined,

a(G₂), b(G₂), . . . , and k(G₂) are the output module(s) in multicast group G₂, and

c₂ is the class of the given data segment,

and wherein the data sent from said second input module during said given prior time period includes at least one data segment replicated by said multicast replicator for output to more than one of said output modules.

49. A method according to claim 41, wherein said set of one or more classes includes more than one class.

50. A method according to claim 49, wherein said classes in said set of classes are classes of service.

51. A method according to claim 49, wherein said set of one or more classes includes a time-sensitive class of data, a bandwidth provisioned class of data and a best-efforts class of data.

52. A method according to claim 49, for use with a plurality of queues of incoming data segments, each of said queues receiving data of a respective one of said classes,

further comprising the step of said input module selecting said each subject data segment from among said queues according to a predetermined priority order of said classes.

53. A method according to claim 41, further comprising, in conjunction with the sending of a given one of said subject data segments in said step of sending,

the step of increasing the number of bytes of data indicated by each of said q(ii, jj=a(GG), cc), q(ii, jj=b(GG), cc), . . . , and q(ii, jj=k(GG), cc), relative to all other q(ii, jj, cc), by the number of bytes in the given data segment,

where ii is the intermediate stage module through which the given data segment is sent,

GG is the multicast group of output modules to which the given data segment is destined,

a(GG), b(GG), . . . , and k(GG) are the output modules in multicast group GG,

and cc is the class of said given data segment.

54. A method according to claim 53, wherein said step of increasing the number of bytes of data indicated by each of said q(ii, jj=a(GG), cc), q(ii, jj=b(GG), cc), . . . , and q(ii, jj=k(GG), cc), relative to all other q(ii, jj, cc), by the number of bytes in the given data segment, comprises the step of increasing the number of bytes of data indicated by each of said q(ii, jj=a(GG), cc), q(ii, jj=b(GG), cc), . . . , and q(ii, jj=k(GG), cc), by the number of bytes in the given data segment.

55. A method according to claim 53, wherein all of the data segments sent in said step of sending are data blocks of constant length,

and wherein said step of increasing the number of bytes of data indicated by each of said q(ii, jj=a(GG), cc), q(ii, jj=b(GG), cc), . . . , and q(ii, jj=k(GG), cc), relative to all other q(ii, jj, cc), comprises the step of incrementing each of said q(ii, jj=a(GG), cc), q(ii, jj=b(GG), cc), . . . , and q(ii, jj=k(GG), cc) by 1 relative to all other q(ii, jj, cc).

56. A method according to claim 41, further comprising, in conjunction with the sending of each given one of said subject data segments in said step of sending,

the step of increasing the number of bytes of data indicated by each of said q(ii, jj=a(GG), cc), q(ii, jj=b(GG), cc), . . . , and q(ii, jj=k(GG), cc), relative to all other q(ii, jj, cc), by the number of bytes in the given data segment,

where ii is the intermediate stage module through which the given data segment is sent,

GG is the multicast group of output modules to which the given data segment is destined,

a(GG), b(GG), . . . , and k(GG) are the output modules in multicast group GG,

and cc is the class of said given data segment.

57. A method according to claim 41, wherein said particular prior time period is an immediately prior time period.

58. A method according to claim 41, wherein the data path from said first input module to an ii'"'"'th one of said intermediate stage modules includes a first plurality of data links,

wherein said step of sending each subject data segment via intermediate module i comprises, for a given one of said subject data segments to be sent via intermediate stage module ii, the step of selecting a given one of said data links on which to send said given data segment.

59. A method according to claim 41, wherein the data path from said first input module to an ii'"'"'th one of said intermediate stage modules includes a first plurality of data links,

wherein the data path from said ii'"'"'th intermediate stage module to a destination output module to which said given data segment is destined includes a second plurality of data links each corresponding to a respective data link in said first plurality of data links,

and wherein said step of sending each subject data segment via intermediate module i comprises, for each given one of said subject data segments to be sent via intermediate stage module ii, the step of selecting a respective given one of said data links on which to send said given data segment,

further comprising the step of said ii'"'"'th intermediate stage module forwarding said given data segment toward said destination output module on the data link in said second plurality of data links that corresponds to the given data link in said first plurality of data links.

60. A method according to claim 41, wherein one of said intermediate stage modules comprises a plurality of input sub-modules in an input sub-stage, a plurality of output sub-modules in an output sub-stage, and a plurality of intermediate sub-modules in an intermediate sub-stage, each of the input sub-modules having a data path to each of said intermediate sub-modules and each of said intermediate sub-modules having a data path to each of said output sub-modules.

61. A method according to claim 41, further for routing data segments from said first input module to a further stage downstream of said plurality of output modules,

further comprising the step of routing data segments originating from said first input module and reaching one of said output modules, to a module in said further stage.

62. Striping apparatus for use in routing segments of data belonging to a class of a set of one or more classes, from a first input module to a plurality of output modules via a plurality of intermediate stage modules, including data segments destined for more than one of said output modules, said first input module having a data path to each of said intermediate stage modules and each of said intermediate stage modules having a data path to each of said output modules, at least one of said intermediate stage modules including a multicast replicator for outputting a data segment received from an input module to more than one of said output modules, the striping apparatus sending each subject data segment of a plurality of subject data segments via intermediate stage module i, where i minimizes

q(i,j=a(G),c)+q(i,j=b(G),c)+ . . . + q(i,j=k(G),c),

where:

q(i, j, c) indicates the number of bytes of data of each class c sent, during a particular prior time period, from said first input module to each j'"'"'th one of said output modules via each i'"'"'th one of said intermediate stage modules,

G is a multicast group of at least one output module to which the subject data segment is destined,

a(G), b(G), . . . , and k(G) are the output module(s) in multicast group G, and

c is the class of the subject data segment.

63. Apparatus according to claim 62, wherein all of said data segments are data blocks of constant length.

64. Apparatus according to claim 62, wherein not all data segments of class c sent during said particular prior time period from said first stage module to output module a(G) are of constant length.

65. Apparatus according to claim 62, for use in routing segments of data from a plurality of input modules to said plurality of output modules via said plurality of intermediate stage modules, said plurality of input modules including said first input module, and each input module in said plurality of input modules having a data path to each of said intermediate stage modules.

66. Apparatus according to claim 65, comprising an integrated circuit chip on which is disposed both said first input module and one of said output modules.

67. Apparatus according to claim 62, further for routing segments of data belonging to a class in said set of one or more classes, from a second input module to said plurality of output modules via said plurality of intermediate stage modules, said second input module having a data path to each of said intermediate stage modules, the striping apparatus sending each given data segment from said second input module via intermediate stage module i₂, where i₂ minimizes

q₂(i₂,j₂=a(G₂),c₂)+q₂(i₂,j₂=b(G₂),c₂)+ . . . +q₂(i₂,j₂=k(G₂),c₂);

where;

q₂(i₂, j₂, c₂) indicates the number of bytes of data of each class c₂ sent, during a given prior time period, from said second input module to each j₂'"'"'th one of said output modules via each i₂'"'"'th one of said intermediate stage modules,

G₂ is a multicast group of at least one output module to which the given data segment is destined,

a(G₂), b(G₂), . . . , and k(G₂) are the output module(s) in multicast group G₂, and

c₂ is the class of the given data segment.

68. Apparatus according to claim 62, further comprising history logic which, in conjunction with selection of a route by said striping apparatus for a given one of said subject data segments, increases the number of bytes of data indicated by each of said q(ii, jj=a(GG), cc), q(ii, jj=b(GG), cc), . . . , and q(ii, jj=k(GG), cc), relative to all other q(ii, jj, cc), by the number of bytes in the given data segment,

where ii is the intermediate stage module through which the given data segment is sent,

GG is the multicast group of output modules to which the given data segment is destined,

a(GG), b(GG), . . . , and k(GG) are the output modules in multicast group GG,

and cc is the class of said given data segment.

69. Apparatus according to claim 68, wherein said history logic increases the number of bytes of data indicated by each of said q(ii, jj=a(GG), cc), q(ii, jj=b(GG), cc), and q(ii, jj=k(GG), cc), by the number of bytes in the given data segment.

70. Apparatus according to claim 62, further comprising history logic which, in conjunction with selection of a route by said striping apparatus for each given one of said subject data segments, increases the number of bytes of data indicated by each of said q(ii, jj=a(GG), cc), q(ii, jj=b(GG), cc), . . . , and q(ii, jj=k(GG), cc), relative to all other q(ii, jj, cc), by the number of bytes in the given data segment,

where ii is the intermediate stage module through which the given data segment is sent,

GG is the multicast group of output modules to which the given data segment is destined,

a(GG), b(GG), . . . , and k(GG) are the output modules in multicast group GG,

and cc is the class of said given data segment.

71. Apparatus according to claim 62, wherein said particular prior time period is an immediately prior time period.

72. Apparatus according to claim 62, wherein the data path from said first input module to an ii'"'"'th one of said intermediate stage modules includes a first plurality of data links,

wherein said striping apparatus, for a given one of said subject data segments to be sent via intermediate stage module ii, selects a given one of said data links on which to send said given data segment.

73. Apparatus according to claim 62, wherein the data path from said first input module to an ii'"'"'th one of said intermediate stage modules includes a first plurality of data links,

wherein the data path from said ii'"'"'th intermediate stage module to a destination output module to which said given data segment is destined includes a second plurality of data links each corresponding to a respective data link in said first plurality of data links,

and wherein said striping apparatus, for each given one of said subject data segments to be sent via intermediate stage module ii, selects a respective given one of said data links on which to send said given data segment,

and further comprising an intermediate stage striper which forwards said given data segment toward said destination output module on the data link in said second plurality of data links that corresponds to the given data link in said first plurality of data links.

74. A method for routing segments of data belonging to a class of a set of one or more classes, from a first input module to a plurality of output modules via a plurality of routes through an intermediate stage, said first input module having a plurality of output ports toward said intermediate stage and said intermediate stage including at least one multicast replicator for outputting a data segment received from an input module to more than one of said output modules, comprising the step of said first input module sending each subject data segment of a plurality of subject data segments via its output port i, where i minimizes

q(i,j=a(G),c)+q(i,j=b(G),c)+ . . . +q(i,j=k(G),c),

where:

q(i, j, c) indicates the number of bytes of data of each class c sent, during a particular prior time period, from said first input module to each j'"'"'th one of said output modules via each i'"'"'th one of said output ports of said first input module,

G is a multicast group of at least one output module to which the subject data segment is destined,

a(G), b(G), . . . , and k(G) are the output module(s) in multicast group G, and

c is the class of the subject data segment,

and wherein the data sent from said first input module during said particular prior time period includes at least one data segment replicated by said at least one multicast replicator for output to more than one of said output modules.

75. Striping apparatus for a fabric having a first input module connected to an intermediate stage connected to a plurality of output modules, the striping apparatus for use in routing segments of data belonging to a class of a set of one or more classes, from the first input module to the plurality of output modules via a plurality of routes through the intermediate stage, including data segments destined for more than one of said output modules, said first input module having a plurality of output ports toward said intermediate stage and said intermediate stage including at least one multicast replicator for outputting a data segment received from an input module to more than one of said output modules, the striping apparatus sending each subject data segment of a plurality of subject data segments via output port i of said first input module, where i minimizes

q(i,j=a(G),c)+q(i,j=b(G),c)+ . . . +q(i,j=k(G),c),

where:

q(i, j, c) indicates the number of bytes of data of each class c sent, during a particular prior time period, from said first input module to each j'"'"'th one of said output modules via each i'"'"'th one of said output ports of said first input module,

G is a multicast group of at least one output module to which the subject data segment is destined,

a(G), b(G), . . . , and k(G) are the output module(s) in multicast group G, and

c is the class of the subject data segment.

76. A method for forwarding segments of data belonging to a class of a set of one or more classes, from a first input module in an input stage to output modules in an output stage via a plurality of routes, comprising the steps of said first input module:

queuing a plurality of data segments of said class in said first module, each of said data segments having a respective group of at least one destination output module;

transmitting data segments from said plurality of data segments via said routes;

receiving acknowledgments each indicating receipt by an output module of a number x of data segments that originated from said first input module;

selecting a subject next data segment from among only those of said queued data segments whose group of destination output modules does not include any particular output module from which an acknowledgment has not yet been received by said first input module covering the y'"'"'th previously sent data segment of said class sent from said first input module and destined for said particular output module, y>

x; and

transmitting said subject next data segment via an i'"'"'th one of said routes, where i minimizes

q(i,j=a(G),c)+q(i,j=b(G),c)+ . . . +q(i,j=k(G),c),

where;

q(i, j, c) indicates the number of bytes of data of said class sent, during a given prior time period, from said first input module to each j'"'"'th one of said output modules via each i'"'"'th one of said routes,

a(G), b(G), . . . , and k(G) are the output module(s) to which said subject next data segment is destined, and

c is the class of said subject next data segment.

77. A method according to claim 76, wherein said step of transmitting data segments from said plurality of data segments comprises the step of, for each particular data segment transmitted in said step of transmitting data segments from said plurality of data segments,

transmitting said particular data segment via an ii'"'"'th one of said routes, where ii minimizes

q(ii,jj=a(GG),c)+q(ii,jj=b(GG),c)+ . . . +q(ii,jj=k(GG),c),

where:

q(ii, jj, c) indicates the number of bytes of data of said class sent, during a respective prior time period, from said first input module to each jj'"'"'th one of said output modules via each ii'"'"'th one of said routes, and

a(GG), b(GG), . . . , and k(GG) are the output module(s) to which said particular data segment is destined.

78. A method according to claim 76, wherein the data segments transmitted in said step of transmitting data segments from said plurality of data segments, prior to said step of selecting a subject next data segment, include at least one data segment destined for more than one of said output modules.

79. A method according to claim 76, wherein the data segments sent from said first input module during said given prior time period include at least one data segment destined for more than one of said output modules.

80. A method according to claim 79, wherein the data segments transmitted in said step of transmitting data segments from said plurality of data segments, prior to said step of selecting a subject next data segment, include at least one data segment destined for more than one of said output modules.

81. Switching apparatus comprising:

a plurality of input modules and a plurality of output modules;

a plurality of intermediate stage modules, each intermediate stage module including a multicast replicator for forwarding a data segment received from an input module to more than one of said output modules;

data paths interconnecting each of said input modules with each of said intermediate stage modules and each of said intermediate stage modules with each of said output modules, said input modules transmitting data segments toward said output modules via said intermediate stage modules; and

a striping mechanism which determines, for each subject one of said data segments, a respective one of said intermediate stage modules via which the subject data segment should be transmitted, wherein;

said striping mechanism is distributed across all of said input modules; and

said striping mechanism comprises a path select mechanism in each of said input modules, the path select mechanism in each given one of said input modules selecting intermediate stage modules for only those of said subject data segments being transmitted by said given input module, and without considering any history of path selections made by any others of said input modules.

82. Apparatus according to claim 81, wherein said switching apparatus is such that the data segments transmitted from said input modules need not be of fixed size.

83. Apparatus according to claim 82, wherein said switching apparatus further is such that the data segments transmitted from said input modules need not be of variable size.

84. Apparatus according to claim 81, wherein one of said subject data segments is destined for more than one of said output modules.

85. Apparatus according to claim 81, wherein the path select mechanism in each given one of said input modules selects intermediate stage modules for those of said subject data segments being transmitted by said given input module, in dependence upon a history of path selections made previously by the path select mechanism in the given input module.

86. Apparatus according to claim 85, wherein the path select mechanism in said given input module selects intermediate stage modules further in dependence upon a history of routes, taken by multicast data segments originating from said given input module, from intermediate stage modules to more than one output module.

87. Apparatus according to claim 81, wherein said striping mechanism comprises a path select mechanism in each of said input modules, the path select mechanism in each given one of said input modules comprising:

a mechanism for maintaining a measure of relative channel loading of routes from said each given input module to output modules, due to data that originated from said each given input module during a given prior time period, said measure of relative channel loading reflecting relative channel loading of each of the routes taken by multicast data segments originating from said each given input module; and

a path select mechanism which, in dependence upon said measure of relative channel loading, determines a given one of said intermediate stage modules through which to send at least a subset of next data segments to be sent by said each given input module.

88. Apparatus according to claim 81, wherein each input module in said plurality of input modules is disposed on a single integrated circuit chip with a respective one of said output modules.

89. A combination of first and second data switches connected either in series or in parallel in a data network, each of said data switches comprising:

a plurality of input modules and a plurality of output modules;

a plurality of intermediate stage modules, each intermediate stage module in each subject one of said data switches including a multicast replicator for forwarding a data segment received from an input module in said subject data switch to more than one of said output modules in said subject data switch;

data paths interconnecting each of said input modules with each of the intermediate stage modules in the same data switch and each of said intermediate stage modules with each of said output modules in the same data switch, said input modules transmitting data segments toward the output modules in the same data switch via the intermediate stage modules in the same data switch; and

a striping mechanism in each given one of said data switches, distributed across all of the input modules in the given data switch, which determines, for each data segment transmitted from an input module in the given data switch, a respective one of said intermediate stage modules in the given data switch via which the data segment should be transmitted,

wherein all of the input modules in both said first and second data switches are identical in the logic they contain,

and wherein the number of input modules contained in said second data switch differs from the number of input modules contained in said first data switch.

90. A combination according to claim 89, wherein all of the intermediate stage modules in both said first and second data switches are identical in the logic they contain,

and wherein the number of intermediate stage modules contained in said second data switch differs from the number of intermediate stage modules contained in said first data switch.

91. A combination according to claim 89, wherein all of modules in both said first and second data switches are identical in the logic they contain.

92. A combination according to claim 89, wherein both said first and second data switches are non-blocking.

93. A combination according to claim 89, wherein said second data switch has twice as many input modules than said first data switch.

94. A combination according to claim 93, wherein said second data switch further has twice as many intermediate stage modules as said first switch.

95. A combination according to claim 94, wherein each of the data paths interconnecting an input stage module with an intermediate stage module has half the data rate in said second data switch than in said first data switch.

96. A combination according to claim 94, further including a third data switch comprising:

a plurality of input modules and a plurality of output modules;

a plurality of intermediate stage modules; and

data paths interconnecting each of said input modules in said third data switch with each of said intermediate stage modules in said third data switch and each of said intermediate stage modules in said third data switch with each of said output modules in said third data switch, said input modules in said third data switch transmitting data segments toward said output modules in said third data switch via said intermediate stage modules in said third data switch,

wherein all of the input modules in both said second and third data switches are identical in the logic they contain,

wherein all of the intermediate stage modules in both said second and third data switches are identical in the logic they contain,

wherein said third data switch has twice as many input modules as said second data switch and twice as many intermediate stage modules as said second switch,

and wherein each of the data paths interconnecting an input stage module with an intermediate stage module has half the data rate in said third data switch as in said second data switch.

97. Apparatus according to claim 89, wherein each input module is disposed on a single integrated circuit chip with a respective one of the output modules in the same data switch.

98. A method comprising the steps of:

providing a plurality of input modules and a plurality of output modules for each of first and second data switches connected either in series or in parallel in a data network;

providing a plurality of intermediate stage modules for each of first and second data switches, each intermediate stage module provided for each subject one of said data switches including a multicast replicator for forwarding a data segment received from an input module provided for said subject data switch to more than one of the output modules provided for said subject data switch;

each of first and second data switches having data paths interconnecting each of the input modules with each of the intermediate stage modules in the same data switch and each of the intermediate stage modules with each of the output modules in the same data switch, the input modules transmitting data segments toward the output modules in the same data switch via the intermediate stage modules in the same data switch; and

providing a striping mechanism for each given one of said data switches, distributed across all of the input modules provided for the given data switch, which determines, for each data segment transmitted from an input module in the given data switch, a respective one of said intermediate stage modules in the given data switch via which the data segment should be transmitted,

wherein all of the input modules provided for both said first and second data switches are identical in the logic they contain,

and wherein the number of input modules provided for said second data switch differs from the number of input modules provided for said first data switch.

99. A method according to claim 98, wherein all of the intermediate stage modules provided for both said first and second data switches are identical in the logic they contain,

and wherein the number of intermediate stage modules provided for said second data switch differs from the number of intermediate stage modules provided for said first data switch.

100. A method according to claim 98, wherein all of modules provided for both said first and second data switches are identical in the logic they contain.

101. A method according to claim 98, wherein both said first and second data switches are non-blocking.

102. A method according to claim 98, wherein the number of input modules provided for said second data switch is twice as large as the number of input modules provided for said first data switch.

103. A method according to claim 102, wherein the number of intermediate stage modules provided for said second data switch is twice as large as the number of intermediate stage modules provided for said first switch.

104. A method according to claim 103, wherein each of the data paths interconnecting an input stage module with an intermediate stage module has half the data rate in said second data switch than in said first data switch.

105. A method according to claim 103, further comprising the step of:

providing for a third data switch a plurality of input modules and a plurality of output modules;

providing for said third data switch a plurality of intermediate stage modules,

said third data switch having data paths interconnecting each of the input modules in said third data switch with each of the intermediate stage modules in said third data switch and each of the intermediate stage modules in said third data switch with each of the output modules in said third data switch, said input modules in said third data switch transmitting data segments toward said output modules in said third data switch via said intermediate stage modules in said third data switch,

wherein all of the input modules provided for both said second and third data switches are identical in the logic they contain,

wherein all of the intermediate stage modules provided for both said second and third data switches are identical in the logic they contain,

wherein the number of input modules provided for said third data switch is twice as large as the number of input modules provided for said second data switch,

wherein the number of intermediate stage modules provided for said third data switch is twice as large as the number of intermediate stage modules provided for said second switch,

and wherein each of the data paths interconnecting an input stage module with an intermediate stage module has half the data rate in said third data switch as in said second data switch.

106. Switching apparatus comprising:

a plurality of input modules and a plurality of output modules;

a plurality of intermediate stage modules, each intermediate stage module including a multicast replicator for forwarding a data segment received from an input module to more than one of said output modules;

data paths interconnecting each of said input modules with each of said intermediate stage modules and each of said intermediate stage modules with each of said output modules, said input modules transmitting data segments toward said output modules via said intermediate stage modules; and

a striping mechanism which determines, for each subject one of said data segments, a respective one of said intermediate stage modules via which the subject data segment should be transmitted, wherein;

said striping mechanism is distributed across all of said input modules;

said striping mechanism comprises a path select mechanism in each of said input modules, the path select mechanism in each given one of said input modules comprising;

a mechanism for maintaining a measure of relative channel loading of routes from said each given input module to output modules, due to data that originated from said each given input module during a given prior time period, said measure of relative channel loading reflecting relative channel loading of each of the routes taken by multicast data segments originating from said each given input module; and

a path select mechanism which, in dependence upon said measure of relative channel loading, determines a given one of said intermediate stage modules through which to send at least a subset of next data segments to be sent by said each given input module.