Two-dimensional circulating switch

1. At a scheduler comprising a processor and a memory device having stored thereon processor-executable instructions, said scheduler coupled to a two-dimensional circulating switch comprising a plurality of switch modules and a plurality of rotators, each rotator cyclically interconnecting a respective subset of at least three switch modules, a method of scheduling data transfer among said switch modules comprising:

creating, for each rotator, an availability matrix indicating availability of paths traversing said each rotator during a rotation cycle having a predefined number of rotation phases;

determining route sets, each route set comprising routes for a respective directed switch-module pair, each route traversing at least one rotator;

determining specific rotators traversed by a selected route from a source switch module to a destination switch module;

and

examining availability matrices corresponding to said specific rotators to determine availability of said selected route.

2. The method of claim 1 further comprising:

determining for each route of said route sets a respective switching delay; and

associating said respective switching delay with said each route.

3. The method of claim 2 further comprising:

sorting constituent routes within said each route set in an ascending order according to a number of rotators traversed by each of said constituent routes to produce a first sorted route set;

sorting routes within said first sorted route set in an ascending order according to switching delay to produce a second sorted route set; and

starting with a first route of said second sorted route set, selecting a first available route within said second sorted route set for a connection of said respective directed switch-module pair.

4. The method of claim 1 further comprising:

setting a scheduling cycle to equal said rotation cycle; and

dividing each rotation phase, of said predefined number of rotation phases, into an integer number of time slots, each time slot being of sufficient duration for transferring a data segment from among a set of data segments each of a same predefined size.

5. The method of claim 4 further comprising transferring from said source switch module multiple data segments having arbitrary destination switch modules during a rotation phase.

6. The method of claim 4 further comprising:

receiving a request to schedule a connection from said source switch module to said destination switch module, said request specifying a requisite flow rate for the connection;

determining a flow-rate unit as said predefined size divided by a period of said scheduling cycle; and

dividing said requisite flow rate by said flow-rate unit to determine a requisite integer number of time slots per scheduling cycle, said requisite integer number at least sufficient to provide said requisite flow rate.

7. The method of claim 6 further comprising:

selecting a candidate route from a pertinent route set connecting said source switch module to said destination switch module;

determining a number of allocable time slots in said candidate route; and

where said number of allocable time slots is less than said requisite integer number of time slots, selecting a supplemental candidate route from said pertinent route set.

8. The method of claim 1 further comprising setting a scheduling cycle to equal an integer multiple of said rotation cycle.

9. The method of claim 1 further comprising:

determining whether said directed switch-module pair connects to common rotators;

where said directed switch-module pair connects to common rotators:

determining zero-order routes connecting the directed switch-module pair, each zero order route traversing one of said common rotators; and

determining first-order routes connecting the directed switch-module pair, each first-order route sequentially traversing two of said common rotators;

where a first switch module of said directed switch-module pair connects to a first set of rotators and a second switch module of said directed switch-module pair connects to a second set of rotators not intersecting said first set of rotators:

determining first-order routes connecting the directed switch-module pair, each first-order route sequentially traversing one rotator of said first set of rotators and one rotator of said second set of rotators; and

determining second-order routes connecting the directed switch-module pair, each second-order route sequentially traversing one rotator of said first set of rotators, one intermediate rotator from among said plurality of rotators, and one rotator of said second set of rotators.