Data burst scheduling

• US 7,215,666 B1
• Filed: 11/13/2001
• Issued: 05/08/2007
• Est. Priority Date: 11/13/2001
• Status: Expired due to Fees

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Jamoussi, Bilel N., Beshai, Maged E.
• Primary Examiner(s): Nguyen, Chau
• Assistant Examiner(s): Cho, Hong Sol
• Application Number:
  US10/054,362
• Time in Patent Office: 2,002 Days
• Field of Search: 370/230, 370/360, 370/369, 370/380, 398/48, 398/60, 398/69
• 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.

Claims

1. A burst-switching network comprising:

a plurality of source nodes;

a plurality of upstream links coupled to said plurality of source nodes;

a plurality of sink nodes;

a plurality of downstream links coupled to said plurality of sink nodes;

a plurality of core nodes, at least one of said plurality of core nodes is coupled to a subset of said plurality of upstream links and a subset of said plurality of downstream links and has a plurality of space switches, each space switch having a slave controller; and

a plurality of master controllers in each core node, one said master controller associated with each of said plurality of space switches in each of said plurality of core nodes and a designated one of said master controllers in a core node functions as a core-node controller, said core-node controller communicatively connecting to each of said master controllers,

said core-node controller operable to;

receive control data from at least one of said plurality of source nodes;

divide said control data among said master controllers; and

instruct each master controller to generate a burst-switching schedule for a space switch associated with said each master controller, communicate said schedule to a respective edge node, and transmit instructions based on said schedule to a slave controller of said space switch after a pre-calculated delay period.

2. The network of claim 1 wherein each of said plurality of source nodes is paired with a corresponding one of said plurality of sink nodes to form a plurality of network edge nodes.

3. The network of claim 2 wherein at least one of said plurality of space switches is an optical switch.

4. The network of claim 3 wherein any of said master controllers can be designated to function as a core-node controller.

5. The network of claim 4 wherein said pre-calculated delay period exceeds the round-trip delay between said core node and said respective edge node.

6. The network of claim 4 wherein each of said master controllers includes a burst scheduler.

7. The network of claim 6 wherein said burst scheduler computes a burst-transfer schedule for a plurality of space switches.

8. The network of claim 7 wherein each of said space switches has a plurality of burst-mode input ports, from each of which individual data bursts are directed to output ports of the space switch, and a plurality of channel-mode input ports, the entire data from each of which is directed to a respective output port of the space switch.

9. The burst-switching network of claim 1 wherein each of said plurality of master controllers comprises:

an input interface for receiving upstream control bursts from a source node;

an input interface to receive control data from a core-node controller;

a burst scheduler for generating a schedule for operation of at least one space switch;

an output interface for communicating said schedule to a sink node associated with said source node;

a transmitter operative to transmit instructions to a slave controller of each of said at least one space switch, where said instructions are based on said schedule; and

a device to acquire timing data from an upstream control burst.

10. A method of scheduling in a bufferless space switch having a plurality of burst-mode input ports, the method comprising steps of:

a. receiving burst descriptors associated with each of the plurality of burst-mode input ports;

b. placing said burst descriptors in bursts queues, at least one burst queue being associated with each one of said plurality of burst-mode input ports;

c. cyclically accessing said burst queues, determining input free time for each burst queue and selecting a maximum of Q candidate burst descriptors;

d. determining output free time for output port indicated in each candidate burst descriptor;

e. determining the absolute value W of the difference between an output free time and an input free time corresponding to each of the Q burst descriptors;

f. selecting a specific candidate burst yielding the least value W; and

g. forwarding the specific candidate burst.

11. The method of claim 10 including the further step of determining said burst descriptors at edge nodes in a closed-loop burst-transfer-control system.

12. The method of claim 10 including the further step of determining said burst descriptors at core nodes in a closed-loop burst-transfer-control system.

13. The method of claim 12 where each of said burst descriptors is associated with a burst stream and said determining is based on a bitrate allocation for said burst stream.

14. A burst scheduler for a space switch, said space switch having a plurality of input ports and a plurality of output ports, said scheduler including:

a receiver for receiving burst descriptors and placing each of said burst descriptors in one of a plurality burst-descriptor memories, each of said burst descriptors identifying an input port, an output port, and a burst size;

an input-state memory for storing next available time of each of said input ports;

a plurality of output-state memories, each storing next-available time of each of said output ports;

a processing circuit including a scheduler kernel for computing a schedule for burst-transfer across said space switch over a predefined period of time T, said processing circuit operable to

select a number Q of candidate burst descriptors for each input port, where Q is an integer greater than zero;

compare corresponding entries in said input-state memory and said plurality of output-state memories for each of said Q candidate burst descriptors and determine a corresponding merit index; and

select one of said Q candidate burst descriptors according to said merit index; and

a permits buffer for storing said schedule.

15. The burst scheduler of claim 14 wherein said merit index is based on an absolute value of the difference between said corresponding entries.

16. The burst scheduler of claim 14 wherein each of said burst-descriptor memories is operative to store burst descriptors belonging to a subset of burst-switching input ports.

17. The burst scheduler of claim 14 wherein the output-state memories have identical content.

18. The burst scheduler of claim 14 wherein the output-state memories are read concurrently at arbitrary memory addresses.

19. In a core node having a plurality of space switches operated in parallel, each of said plurality of space switches having a plurality of input ports, a plurality of output ports, and a master controller with one said master controller designated to function as a core-node controller, said core node switching burst streams from a plurality of upstream links, each having multiple wavelength channels, to a plurality of downstream links, each having multiple wavelength channels, a method of confining connections from each upstream link to each downstream link to a small number of space switches, the method comprising the steps of:

receiving a bitrate requirement for each connection;

sorting received bitrate requirements associated with each upstream link in a descending order according to bitrate value;

implementing a cyclic allocation of said requirements to corresponding paths of the space switches, retaining a remainder when one of said corresponding paths is exhausted, and determining a progress indicator; and

repeating said cyclic allocation if permitted by said progress indicator.