Burst switching in a high capacity network

• US 6,907,002 B2
• Filed: 12/29/2000
• Issued: 06/14/2005
• Est. Priority Date: 12/29/2000
• Status: Expired due to Fees

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Vickers, Richard, Beshai, Maged E.
• Primary Examiner(s): Sam, Phirin
• Assistant Examiner(s): TON, ANTHONY T
• Application Number:
  US09/750,071
• Publication Number:
  US 20020085491A1
• Time in Patent Office: 1,628 Days
• Field of Search: 370/235.1, 370/236.1, 370/236.2, 370/230, 370/231, 370/232, 370/233, 370/234, 370/235, 370/236, 370/237, 370/238, 370/239, 370/240, 370/380, 370/357, 370/358, 370/360, 370/381, 370/389, 370/230.1
• US Class Current: 370/230
• CPC Class Codes: H04Q 11/0066 Provisions for optical burst or packet networks
• CPC Class Codes: H04Q 11/06 Time-space-time switching
• CPC Class Codes: H04Q 2011/0039 Electrical control
• CPC Class Codes: H04Q 2011/0064 Arbitration, scheduling or medium access control aspects
• CPC Class Codes: H04Q 2011/0088 Signalling aspects
• CPC Class Codes: H04Q 2213/1305 Software aspects
• CPC Class Codes: H04Q 2213/13103 Memory
• CPC Class Codes: H04Q 2213/13106 Microprocessor, CPU
• CPC Class Codes: H04Q 2213/13164 Traffic (registration, measurement,...)
• CPC Class Codes: H04Q 2213/13166 Fault prevention
• CPC Class Codes: H04Q 3/0091 Congestion or overload control

Abstract

At a master controller of a space switch in a node in a data network, a request is received from a source node that requests a connection to be established through the space switch. This request is compared to other such requests so that a schedule may be established for access to the space switch. The schedule is then sent to the source nodes as well as to a slave controller of the space switch. The source nodes send data bursts which are received at the space switch during a short guard time between successive reconfigurations of the space switch. Data bursts are received at the space switch at a precisely determined instant of time that ensures that the space switch has already reconfigured to provide requested paths for the individual bursts. The scheduling is pipelined and performed in a manner that attempts to reduce mismatch intervals of the occupancy states of input and output ports of the space switch. The method thus allows efficient utilization of the data network resources while ensuring virtually no data loss.

Claims

1. A method of controlling a space switch having a plurality of input ports and a plurality of output ports, said method comprising:

receiving a stream of burst transfer requests, each of said burst transfer requests specifying one of said input ports, one of said output parts, and a corresponding burst duration;

grouping said burst transfer requests into burst groups according to their corresponding input ports;

generating schedules for said burst transfer requests in an order in which input ports corresponding to said burst transfer requests become unoccupied;

transmitting said schedules to sources of said burst-transfer requests; and

transmitting said schedules and corresponding burst-transfer requests to a slave controller for said space switch, to set up paths through said space switch.

2. The method of claim 1 wherein said generating comprises:

determining a next-available input port to be considered;

determining a next burst group corresponding to said next-available input port;

if said next burst group includes at least two burst transfer request;

determining a time gap as an availability time of an output port specified in each of said at least two burst transfer requests minus an availability time of said next available input port;

selecting a particular burst transfer request, from said at least two burst transfer requests, which corresponds to a lowest time gap;

if said next burst group includes one burst-transfer request;

identifying said one burst transfer request as a particular burst transfer request; and

determining a starting time at which said space switch establishes a connection from said next-available input port to a particular output port specified in said particular burst-transfer request.

3. The method of claim 2 further comprising:

determining an updated availability time to equal said starting time plus a burst-duration time specified in said particular burst-transfer request;

updating said availability time of said next-available input port to equal said updated availability time; and

updating an availability time of said particular output port to equal said updated availability time.

4. The method of claim 2 wherein, if said next burst group has no burst-transfer requests, updating said availability time of said next-available input port by adding a burst-duration of an artificial burst.

5. A space switch master controller for a space switch comprising:

a source interface for;

receiving a stream of burst transfer requests from a source node, each of said burst transfer requests including parameters specifying a requested connection and a duration for said requested connection;

transmitting scheduling information for each of said burst transfer requests to said source node;

a burst scheduler for generating, in an order in which input ports corresponding to said burst transfer requests become unoccupied, said scheduling information for each of said burst transfer requests in said stream based on said parameters; and

a slave controller interface for transmitting instructions to a slave controller for said space switch, where said instruction are based on said scheduling information and cause said space switch to establish said requested connection.

6. A computer readable medium containing computer-executable instructions which, when performed by a processor in a space switch master controller for a space switch, cause the processor to:

receive a stream of burst transfer requests from a source node, each of said burst transfer requests including parameters specifying a requested connection and a duration for said requested connection;

generate, in an order in which input ports corresponding to said burst transfer requests become unoccupied, scheduling information for each of said burst transfer requests based on said parameters;

transmit said scheduling information to said source node; and

transmit said scheduling information to a slave controller of said space switch.

7. A method of scheduling comprising:

determining a next-available input port among a plurality of input ports and an input time index at which said next-available input port will become available;

for each burst transfer request of a plurality of burst transfer requests received from said next-available input port, where said each burst transfer request includes a duration of a burst and a destination of said burst;

determining, from said destination of said burst, a corresponding output port among a plurality of output ports;

determining a time gap, where said time gap equals a time index as which said corresponding output port will become available minus said input time index;

selecting a particular burst transfer request from said plurality of burst transfer requests where said particular burst transfer request has a minimum time gap; and

determining a scheduled time index, where said scheduled time index equals said time index at which said corresponding output port is available if said time gap is positive, otherwise said scheduled time index equals said input time index.

8. A method of generating scheduling information comprising:

determining a next-available input port among a plurality of input ports and a time index at which said next-available input port will become available by scanning a time calendar until an input port identifier is detected in a time slot, said calendar having a plurality of time slots, where each time slot corresponds to a predefined time interval;

for each burst transfer request of a plurality of burst transfer requests received in relation to said next-available input port, and where said each burst transfer request includes an identity of a burst and a destination for said burst;

determining from said destination for said burst, a corresponding output port among a plurality of output ports;

determining a time gap where said time gap is a difference between;

said time index at which said next-available input port will become available; and

a time index at which said corresponding output will become available;

selecting one of said plurality of burst transfer requests as a selected burst transfer request, where said selected burst transfer request has a minimum time gap of said plurality of burst transfer request;

selecting a scheduled time index, where said scheduled time index is one of said time index at which said next available input port is available and said time index at which said corresponding output port is available; and

transmitting scheduling information for a burst identified by said selected burst transfer request, said scheduling information based on said scheduling time index.

9. The method of claim 8 wherein said determining said time gap comprises reading said time index at which said corresponding output port is available from an element in an array, where said element is associated with said corresponding output port.

10. The method of claim 9 further comprising:

determining, from said selected burst transfer request, a transfer-time for said burst;

adding said transfer-time to said scheduled time index to result in a finishing time index; and

writing said input port identifier in a time slot corresponding to said finishing time index.

11. The method of claim 10 further comprising writing a null identifier in a time slot corresponding to said scheduled time index.

12. The method of claim 11 further comprising writing said finishing time index to said element in said array.

13. The method of claim 12 wherein said array is one of a plurality of arrays and said writing said finishing time index comprises writing said finishing time index to the element that is associated with said corresponding output port in each of said plurality of arrays.

14. The method of claim 13 wherein said writing in each of said plurality of arrays is performed in parallel.

15. The method of claim 12 wherein said time index at which said corresponding output port is available is selected as said scheduled time index.

16. The method of claim 12 wherein a calendar time slot index at which said input port identifier is detected is selected as said scheduled time index.

17. The method of claim 8 wherein said input port identifier is detected only if included in a predetermined group of input port identifiers.

18. The method of claim 17 wherein burst transfer requests are organized by groups of output ports and said determining said time gap is limited to include only those burst transfer requests corresponding to a group of said plurality of output ports.

19. A burst scheduler comprising a processor operable to:

determine a next-available input port among a plurality of input ports and an input time index at which said next-available input port becomes available;

for each burst transfer request of a plurality of burst transfer requests received from said next-available input port, and where said each burst transfer request includes a duration of a burst and a destination of said burst;

determine, from said destination of said burst, a corresponding output port among a plurality of output ports;

determine a time gap, where said time gap equals a time index at which said corresponding output port becomes available minus said input time index;

select a particular one of said plurality of burst transfer requests where said particular one of said plurality of burst transfer requests has a minimum time gap; and

determine a scheduled time index, where said scheduled time index equals said input time index when said time gap is negative and equals said time index at which said corresponding output port is available when said time gap is not negative.

20. A computer readable medium containing computer-executable instructions which, when performed by a processor in a burst scheduler, cause the processor to:

determine a next-available input port among a plurality of input ports and an input time index at which said next-available input port will become available;

for each burst transfer request of a plurality of bust transfer request received in from said next-available input port, and where said each burst transfer request includes a duration of a burst and a destination of said burst;

determine, from said destination of said burst, a corresponding output port among a plurality of output ports;

determine a time gap, where said time gap equals a time index at which said corresponding output port will become available minus said input time index;

select a particular one of said plurality of burst transfer requests where said particular one of said burst transfer requests has a minimum time gap; and

determine a scheduled time index, where said scheduled time index equals said time index at which said corresponding output port is available, if said time gap is positive, and equals said input time index if said time gap is not positive.

21. A data network comprising:

a plurality of edge nodes;

a plurality of core nodes, each core node of said plurality of core nodes including a space switch; and

a master controller for one said space switch in one said core node for;

receiving a stream of burst transfer requests from one of said plurality of edge nodes, each of said burst transfer requests including parameters specifying a requested connection and a duration for said requested connection;

generating, in an order in which input ports corresponding to said burst transfer requests become unoccupied, scheduling information for each of said burst transfer requests based on said parameters;

transmitting said scheduling information to said one of said plurality of edge nodes; and

transmitting said scheduling information to a slave controller of said one said space switch.

22. A master controller of a space switch, said space switch having a plurality of input ports and a plurality of output ports, said master controller operable to:

receive a stream of burst transfer requests, each of said burst transfer requests specifying one of said input ports, one of said output ports, and a corresponding burst duration;

group said burst transfer requests into burst groups, each of said burst groups corresponding to one of said input ports;

generate schedules for said burst transfer requests in an order in which input ports corresponding to said burst transfer requests become unoccupied;

transmit said schedules to sources of said burst-transfer; and

transmit said schedules and corresponding burst-transfer requests to a slave controller of said space switch to set up paths through said space switch.

23. A burst-switching network comprising:

a plurality of core nodes, each of said plurality of core nodes including a bufferless space switch; and

a plurality of edge nodes, each of said plurality of edge nodes having;

a communication link to each of at least one of said plurality of core nodes; and

a data buffer associated with said communications link;

where said each of said plurality of edge nodes is adapted to perform a process for time-locking to each of said at least one of said core nodes; and

wherein said each of said plurality of edge nodes is adapted to;

send a stream of burst-transfer requests to a selected core node of said at least one of said core nodes, where each burst-transfer request of said stream of burst-transfer requests corresponds to a burst having a duration below a specified limit;

receive a stream of burst-transfer schedules from said selected core node; and

transmit bursts corresponding to said burst-transfer requests to said selected core node according to said burst-transfer schedules wherein said burst-transfer schedules are based on a calendar having a predetermined calendar period, where said calendar has been divided into a predetermined number of divisions; and

wherein each of said core nodes includes a master time counter having a predetermined counter period and each of said edges nodes includes a slave time counter having said predetermined counter period, and said process of time locking uses said slave time counter and said master timer counter.

24. The burst-switching network of claim 23 wherein said counter period exceeds a round-trip propagation delay between any of said edge nodes and any of said core nodes.

25. The burst-switching network of claim 23 wherein said counter period is an integer multiple of said calendar period.

26. The burst-switching network of claim 25 wherein said integer multiple equals a first power of two, and said predefined number of divisions equals a second power of two.

27. The burst-switching network of claim 23 wherein said calendar period is selected to at least equal said specified limit.