Data Burst Scheduling

• US 20070171900A1
• Filed: 04/04/2007
• Published: 07/26/2007
• Est. Priority Date: 11/13/2001
• Status: Active Grant

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Bilel Jamoussi, Maged Beshai
• Inventors: Jamoussi, Bilel, Beshai, Maged
• Granted Patent: US 7,590,109 B2
• Time in Patent Office: Days
• US Class Current: 370/380
• CPC Class Codes: H04Q 11/0066 Provisions for optical burst or packet networks
• CPC Class Codes: H04Q 2011/0064 Arbitration, scheduling or medium access control aspects
• CPC Class Codes: H04Q 2011/0088 Signalling aspects

Abstract

A method and apparatus for scheduling the transfer of data bursts in a network comprising electronic edge nodes interconnected by bufferless core nodes are disclosed. Each edge node comprises a source node and a sink node, and each core node comprises several bufferless space switches operated in parallel. Each source node is connected to at least one core node by an upstream link that includes multiple upstream channels. Each core node is connected to at least one sink node by a downstream link that includes multiple downstream channels. Any of the space switches can have either an electronic fabric or a photonic fabric. Each space switch has a master controller, and one of the master controllers in a core node is designed to function as a core-node controller in addition to its function as a master controller. Each master controller has a burst scheduler operable to compute a schedule for the transfer of data bursts, received from source nodes, to destination sink nodes. In one mode of operation, each source node determines the bitrate requirements for paths to each sink node and sends bitrate-allocation requests to a core-node controller. A core-node controller receives requests for bitrate allocations from source nodes and assigns each request to one of the master controllers of the core node. Each master controller then computes burst-transfer permits and sends the permits to corresponding edge nodes. Each permit specifies a burst size, a destination sink node, the time at which the burst should be transmitted from its source node, and the upstream channel to be used. It is emphasized that in this mode of operation, the source node communicates information on burst streams not on individual bursts. In another mode of operation, each source node determines a descriptor of each unscheduled waiting data bursts and communicates the burst descriptors of all unscheduled bursts to a controller of a core node. The core-node controller then directs each burst descriptor to one of the master controllers of the core node which then computes a schedule for burst transfer and sends the schedule to corresponding edge node. The schedule indicates the upstream channel to be used for each burst and the time at which each burst, already waiting at the source node, should be transmitted to the core node. The scalability of the network is determined, in part, by the processing capacity of the burst scheduler and techniques for circumventing this limitation are described in this disclosure.

Claims

1. In a bufferless space switch having a plurality of burst-mode input ports and a plurality of output ports, a method of determining a schedule for switching data bursts, over a designated schedule period T, from said plurality of burst-mode input ports to said plurality of output ports, the method including the step of repetitively employing said schedule for switching data bursts during m consecutive periods, m being an integer greater than zero and each of said consecutive periods is equal to said designated period.

2. The method of claim 1 including the further step of setting m to exceed the ratio of the time required to compute said schedule and said designated schedule period T.

3. The method of claim 2 including the further step of computing said schedule every m consecutive periods.

4. The method of claim 3 including the further step of generating said schedule for a succession of bursts generated over a period T.

5. The method of claim 4 including the further step of generating said succession of bursts according to bitrate allocations for burst streams to be switched from a burst-mode input port to an output port.

6. The method of claim 5 including the further step of refreshing said bitrate allocations periodically every m×

T interval.

7. In a bufferless space switch having a plurality of burst-mode input ports and a plurality of output ports, a method of determining a schedule for switching data bursts, over each of successive time intervals, each time interval having a duration T, from said plurality of burst-mode input ports to said plurality of output ports, comprising the steps of:

setting the computation period for each of said successive time intervals to an integer multiple m of the interval T; and

computing m successive schedules concurrently.

8. The method of claim 7 including the further step of setting the value of m to exceed the time required to compute said schedule for each time interval T divided by the time interval T.

9. The method of claim 8 including the further step of operating at least m scheduling devices concurrently.

10. The method of claim 9 including the further steps of computing said schedule for burst descriptors generated according to bitrate allocations for each pair of burst-mode input port and output port, and refreshing the bitrate allocations at every interval T.

11. A core node having a plurality of space switches, each space switch having burst-mode input ports and channel-mode input ports, wherein each burst-mode input port switches individual data bursts to respective output ports, and each channel-mode input port has a switched channel connection carrying a succession of data units of any format to a single output port.

12. The core node of claim 11 wherein the search for a channel connection starts from the same space switch and follows the same order for each channel connection, and wherein the number of channel connections in a space switch is limited below a predetermined upper bound.

13. The core node of claim 11 wherein the burst connections are allocated equitably among the space switches.