High-speed scheduling apparatus for a switching node
View Patent ↗A scheduling apparatus for a switch includes multiple schedulers which are assigned in a variety of ways to non-intersecting control domains for establishing connections through the switch. The control domains are defined by spatial and temporal aspects. The control domains may be dynamically selected and assigned to schedulers in a manner that achieves a high throughput gain. Control domains may be considered in a cyclic and/or a pipeline discipline for accommodating connection requests. The invention enables the realization of a highly scalable controller of a switching node of fine granularity that scales to capacities of the order of hundreds of terabits per second.
1. A multi-processor scheduling apparatus for facilitating establishment of a connection in a switch fabric having a plurality of input ports and a plurality of output ports in response to receiving connection requests, said plurality of input ports being divided into non-intersecting input-port groups, said apparatus comprising multiple schedulers individually associated with non-intersecting control domains, each of said control domains being bounded by at least one of:
a sub-frame of a repetitive time frame divided into non-intersecting sub-frames;
an input-port group within said plurality of input ports; and
an output-port group within said plurality of output ports;
each scheduler employing at least one processor and accommodates a connection request within a control domain with which said each scheduler is associated;
wherein each control domain is defined by an input-port group from among said non-intersecting input-port groups, said plurality of output ports, and a sub-frame from among said non-intersecting sub-frames, and each of said schedulers is cyclically paired with said each control domain during said time-frame.
2. A multi-processor scheduling apparatus for facilitating establishment of a connection in a switch fabric having a plurality of input ports and a plurality of output ports in response to receiving connection requests, said plurality of output ports being divided into non-intersecting output-port groups, said apparatus comprising multiple schedulers individually associated with non-intersecting control domains, each of said control domains being bounded by at least one of:
a sub-frame of a repetitive time frame divided into non-intersecting sub-frames;
an input-port group within said plurality of input ports; and
an output-port group within said plurality of output ports;
each scheduler employing at least one processor and accommodates a connection request within a control domain with which said each scheduler is associated;
wherein each control domain is defined by said plurality of input ports, an output-port group from among said non-intersecting output-port groups, and a sub-frame from among said non-intersecting sub-frames, and each of said schedulers is cyclically paired with said each control domain during said time-frame.
3. A multi-processor scheduling apparatus for establishing a connection in a switch fabric having a plurality of input ports and a plurality of output ports in response to receiving a succession of connection requests, said apparatus comprising:
a plurality of schedulers, each scheduler employing at least one processor, said schedulers interconnected in a circular pipeline;
a plurality of domain-state memory devices, each domain-state memory device permanently coupled to a respective scheduler and holds occupancy states of each input port of said plurality of input ports and each output port of said plurality of output ports during a respective sub-frame from among non-intersecting sub-frames of a repetitive time frame; and
at least two request buffers, each request buffer holding connection requests and permanently connected to a selected scheduler;
wherein said plurality of schedulers is arranged into scheduler groups and wherein a last scheduler in each scheduler group connects to a request buffer coupled to a scheduler of a subsequent scheduler group.
4. The multi-processor scheduling apparatus of claim 3 wherein said each domain-state memory device comprises a first memory device for holding occupancy state of said each input port during each time slot in said respective sub-frame and a second memory device for holding occupancy state of said each output port during said each time slot.
5. The multi-processor scheduling apparatus of claim 3 further comprising a request distributor for cyclically distributing connection requests originating from said plurality of input ports to individual request buffers of said at least two request buffers.
6. The multi-processor scheduling apparatus of claim 3 wherein each said connection request specifies an input port among said plurality of input ports, an output port among said plurality of output ports, and a number of time slots within said repetitive time frame, and wherein each scheduler produces one of:
an indication of allocated time slots; and
parameters of a scheduling request to be cascaded to a subsequent scheduler.
7. An apparatus for establishing a connection in a switch fabric having a plurality of input ports and a plurality of output ports in response to receiving a succession of connection requests, said apparatus comprising:
a plurality of request buffers, each request buffer receiving connection requests from at least one input port;
a plurality of domain-state memory devices, each domain-state memory device holding occupancy states of each input port of said plurality of input ports and each output port of said plurality of output ports during a respective sub-frame from among non-intersecting sub-frames of a repetitive time frame;
a plurality of schedulers, each scheduler permanently coupled to a respective request buffer and cyclically coupled to said each domain-state memory device; and an equalizing request distributor for equitably offering scheduling requests received from said plurality of input ports to request buffers of said plurality of request buffers so that processing loads are equalized among schedulers of said plurality of schedulers.
8. An apparatus for establishing a connection in a switch fabric having a plurality of input ports and a plurality of output ports in response to receiving a succession of connection requests, said apparatus comprising:
a plurality of request buffers, each request buffer receiving connection requests from at least one input port;
a plurality of domain-state memory devices, each domain-state memory device holding occupancy states of each input port of said plurality of input ports and each output port of said plurality of output ports during a respective sub-frame from among non-intersecting sub-frames of a repetitive time frame; and
a plurality of schedulers, each scheduler permanently coupled to a respective request buffer and cyclically coupled to said each domain-state memory device;
wherein said plurality of input ports is partitioned into a number of input-port groups each input-port group including a respective predefined number of input ports and wherein said each input-port group sends connection requests directed to said plurality of output ports to a respective request buffer among said plurality of request buffers.
9. An apparatus for establishing a connection in a switch fabric having a plurality of input ports and a plurality of output ports in response to receiving a succession of connection requests, said apparatus comprising:
a plurality of request buffers, each request buffer receiving connection requests from at least one input port;
a plurality of domain-state memory devices, each domain-state memory device holding occupancy states of each input port of said plurality of input ports and each output port of said plurality of output ports during a respective sub-frame from among non-intersecting sub-frames of a repetitive time frame; and
a plurality of schedulers, each scheduler permanently coupled to a respective request buffer and cyclically coupled to said each domain-state memory device;
wherein said plurality of output ports is partitioned into a number of output-port groups each output-port group including a respective predefined number of output ports and wherein said plurality of input ports sends connection requests directed to said each output-port group to a respective request buffer among said plurality of request buffers.
10. The apparatus of claim 7 further comprising a cyclic connector for cyclically connecting said each scheduler to said each domain-state memory device.
11. A method of concurrent scheduling of multiple connections implemented by multiple processors coupled to a switch fabric, the method comprising:
defining a set of non-intersecting control domains, each control domain bounded by a set of input ports among a plurality of input ports of said switch fabric, a set of output ports among a plurality of output ports of said switch fabric, and a set of time slots within a predefined repetitive time frame;
storing occupancy states of input ports of said set of input ports and occupancy states of output ports of said set of output ports of said each control domain during said set of time slots in a respective domain-state memory device among a plurality of domain-state memory devices;
coupling said respective domain-state memory device to a respective scheduler from among a plurality of schedulers each employing at least one processor;
cyclic pairing of each request buffer, among a plurality of request buffers holding connection requests, and each domain-state memory device of said plurality of domain-state memory devices; and
allocating multiple connection requests to different schedulers among said plurality of schedulers.
12. The method of claim 11 further comprising cascading schedulers of said plurality of schedulers to form a circular pipeline thereby enabling said cyclic pairing of said each request buffer and said each domain-state memory with permanent coupling of said respective domain-state memory device to said respective scheduler.
13. The method of claim 11 wherein said coupling is cyclical with each domain-state memory device connecting to each scheduler during a repetitive scheduling cycle, thereby enabling said cyclic pairing of said each request buffer and said each domain-state memory device.
14. The method of claim 11 further comprising selecting a duration of said repetitive scheduling cycle to be an integer multiple of a duration of said repetitive time frame.
15. The method of claim 11 further comprising cyclically distributing connection requests originating from said plurality of input ports among request buffers of said plurality of request buffers.
16. The method of claim 11 further comprising equitably distributing connection requests originating from said plurality of input ports among request buffers of said plurality of request buffers according to requisite processing efforts of individual connection requests.
17. The method of claim 11 further comprising one-to-one mapping of scheduled time slots to real-time slots in order to space scheduled time slots of each connection requiring multiple time slots per time frame.