Scheduling in a fast optical switch

1. A method of bimodal pipelined scheduling in a scheduling system, said scheduling system including N scheduler modules, indexed as 1 to N, N>1, arranged in a predatermined order between a first scheduler module of index 1 and a last scheduler module of index N, where each scheduler module is exclusively associated with a pool of resources comprising resources of a first granularity and resources of a second granularity, said method comprising:

receiving a first scheduling request specifying a first amount of resources of said first granularity;

at a selected scheduler module, starting with said first scheduler module of index 1, attempting to allocate resources to satisfy said first scheduling request;

where said attempting at said selected scheduler module fails to completely satisfy said first scheduling request, selecting a subsequent scheduler module according to said predetermined order;

receiving a second scheduling request specifying a second amount of resources of said second granularity;

at an other selected scheduler module, starting with said last scheduler module of index N, attempting to allocate resources to satisfy said second scheduling request; and

where said attempting, at said other scheduler module, fails to completely satisfy said second scheduling request, selecting a preceding scheduler module sequentially following a reverse order towards said first scheduler module.

2. The method of claim 1 wherein said first scheduling request is satisfied by at least one of said scheduler modules and said second scheduling request is satisfied by at least one of said scheduler modules.

3. The method of claim 2 further comprising, at a given scheduler module having received said first scheduling request and said second scheduling request, performing said attempting to allocate resources to satisfy said second scheduling request before performing said attempting to allocate resources to satisfy said first scheduling request.

4. The method of claim 3 wherein, at said given scheduler module, said attempting to allocate resources comprises selecting resources from a pool of allocable resources exclusively associated with said given scheduler module.

5. The method of claim 4 wherein said allocable resources are defined in fine resource units and coarse resource units.

6. The method of claim 5 wherein said first amount of resources is specified in said fine resource units and said second amount of resources is specified in said coarse resource units.

7. The method of claim 6 further comprising:

receiving a third scheduling request including a first request portion specifying an amount of coarse resource units and a second request portion specifying an amount of fine resource units;

at said last scheduler module, attempting to allocate resources to satisfy said first request portion;

where said attempting fails to completely satisfy said first request portion, selecting a preceding scheduler module according to said predetermined order;

at said preceding scheduler module, attempting to allocate resources to satisfy said first request portion;

continuing said attempting to allocate resources to satisfy said first request portion at further preceding scheduler modules, selected according to said predetermined order, until said first request portion is satisfied or said first scheduler module fails to completely satisfy said first request portion;

at said first scheduler module, attempting to allocate resources to satisfy said second request portion;

where said attempting fails to completely satisfy said second request portion, selecting a subsequent scheduler module according to said predetermined order;

at said subsequent scheduler module, attempting to allocate resources to satisfy said second request portion; and

continuing said attempting to allocate resources to satisfy said second request portion at further succeeding scheduler modules, selected according to said predetermined order, until said second request portion is satisfied or said last scheduler module fails to completely satisfy said first request portion.

8. A pipelined scheduling system comprising:

a number N of scheduler modules, N>1, indexed as 1 to N, arranged in a predetermined order between a first scheduler module of index 1 and a last scheduler module of index N; and

a plurality of distinct pools of resources each pool of resources comprising resources of a first granularity and resources of a second granularity, wherein each of said scheduler modules is exclusively associated with a respective pool of resources;

said system operable to:

receive scheduling requests of a first type, each specifying a first amount of resources of said first granularity;

attempt, at said scheduler modules selected in said predetermined order starting from a scheduler module of index 1, to allocate resources to satisfy said scheduling requests of said first type;

receive scheduling requests of a second type, each specifying a second amount of resources of said second granularity; and

attempt, at said scheduler; modules selected sequentially in a reverse order of said predetermined order, starting from a scheduler module of index N, to allocate resources to satisfy said scheduling requests of said second type.

9. The system of claim 8 further comprising:

a forward input buffer associated with each of said scheduler modules for receiving said scheduling requests of said first type; and

a backward input buffer associated with each of said scheduler modules for receiving said scheduling requests of said second type.

10. The system of claim 9 further comprising a result buffer associated with each of said scheduler modules.

11. The system of claim 10 wherein each said scheduler module is operable to, upon successfully allocating given resources to satisfy a given one of said scheduling requests of said first type, pass identifiers of said given resources to said associated result buffer.

12. The system of claim 11 wherein said first scheduler module is operable to:

subtract an amount representative of said given resources from said first amount of resources, specified in said given one of said scheduling requests of said first type, to produce a first remaining amount; and

pass an indication of said first remaining amount to a subsequent scheduler module, said subsequent scheduler module selected according to said predetermined order.

13. The system of claim 11 further comprising a cyclic selector for cyclically accessing said result buffers associated with said scheduler modules to obtain said identifiers of said given resources.

14. The system of claim 10 wherein each said scheduler module is operable to, upon successfully allocating given resources to satisfy a given one of said scheduling requests of said second type, pass identifiers of said given resources to said associated result buffer.

15. The system of claim 14 wherein said last scheduler module is operable to:

subtract an amount representative of said given resources from said second amount of resources, specified in said given one of said scheduling requests of said second type, to produce a second remaining amount; and

pass an indication of said second remaining amount to a preceding scheduler module, said preceding scheduler module selected according to said predetermined order.

16. The system of claim 14 further comprising a cyclic selector for cyclically accessing said result buffers associated with said scheduler modules to obtain said identifiers of said given resources.

17. The system of claim 8 wherein each said scheduler module is further operable to terminate said attempt to allocate resources for a given one of said scheduling requests of said first type when an amount of allocated resources equals said first amount of resources specified by said given one of said scheduling requests.

18. The system of claim 8 wherein said associated pool of resources comprises paths through at least one space switch in a switching node having a plurality of space switches, each space switch of said plurality of space switches having a plurality of input ports and a plurality of output ports.

19. The system of claim 18 wherein said at least one space switch switches both continuous channels and time-slots in time-slotted-channd paths from said input ports to said output ports.

20. The system of claim 19 wherein said first amount of resources is a number of said time slots.

21. The system of claim 19 wherein said second amount of resources is a number of said continuous channels.

22. The system of claim 19 wherein said at least one space switch comprises a star coupler having a plurality of input ports and an output port, said output port connecting, through an optical amplifier, to a wavelength demultiplexer having a plurality of output ports.

23. A method of bimodal pipelined scheduling in a scheduling system, said scheduling system including N scheduler modules, indexed as 1 to N, N>1 , arranged in a predetermined order between a first scheduler module of index 1 and a last scheduler module of index N, where each scheduler module is exclusively associated with a pool of resources comprising resources of a first granularity and resources of a second granularity, said method comprising:

receiving a first scheduling request specifying a first amount of resources of said first granularity;

at said first scheduler module:

determining a first part of a first subset of allocable resources for satisfying said first scheduling request; and

passing a first internal scheduling request, specifying an amount of resources equivalent to said first amount of resources reduced by the amount of resources in said first subset of allocable resources, to a subsequent scheduler module selected according to said predetermined order;

receiving a second scheduling request specifying a second amount of resources of said second granularity;

at said last scheduler module:

determining a first part of a second subset of allocable resources for satisfying said second scheduling request; and

passing a second internal scheduling request, specifying an amount of resources equivalent to said second amount of resources reduced by the amount of resources in said second subset of allocable resources, to a preceding scheduler module of index (N−1) sequentially following a reverse order towards said first scheduler module.

24. The method of bimodal pipelined scheduling of claim 23 wherein said resources of said first granularity are time slots in a time-slotted frame and said resources of said second granularity are wavelenath channels and wherein said first amount of resources comprises an integer number of time slots in a time-shared wavelength channel and said second amount of resources comprises an integer number of wavelength channels.

25. A pipehned scheduling system comprising N scheduler modules, indexed as 1 to N, N>1, arranged in a predetermined order between a first scheduler module of index 1 and a last scheduler module of index N, each scheduler module being exclusrvely associated with a pool of resources comprising resources of a first granularity and resources of a second granularity,

said first scheduler module operable to:

receive a first scheduling request specifying a first amount of resources of said first granularity;

determine a first part of a first subset of allocable resources for satisfying said first scheduling request; and

pass a first internal scheduling request, specifying an amount of resources equivalent to said first amount of resources reduced by the amount of resources in said first subset of allocable resources, to a subsequent scheduler module selected according to said predetermined order;

said last scheduler module operable to:

receive a second scheduling request specifying a second amount of resources of said second granularity;

determine a first part of a second subset of allocable resources for satisfying said second scheduling request; and

pass a second internal scheduling request, specifying an amount of resources equivalent to said second amount of resources reduced by the amount of resources in said second subset of allocable resources, to a preceding scheduler module of index (N−1) sequentially following a reverse order towards said first scheduler module.