Burst switching in a high capacity network

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.

1 . An edge node in a network, said edge node comprising: 
 an edge controller including a slave time counter;    means for time-locking said slave time counter to a master time counter associated with a core node in said network;    means for forming data bursts;    means for associating, with each of said data bursts, indicators of destination and burst duration;    means for communicating said burst-indicators to said core node;    means for receiving burst-transfer schedules from said core node; and    means for transmitting data bursts according to said schedules.    
   
   
       2 . The edge node of  claim 1  wherein said communicating and said transmitting are time interleaved.  
   
   
       3 . The edge node of  claim 1  wherein said communicating and said transmitting are concurrent.  
   
   
       4 . The edge node of  claim 1  wherein each of said data bursts has a duration not exceeding a predetermined limit.  
   
   
       5 . The edge node of  claim 4  wherein said schedules are determined with reference to a calendar of fixed calendar duration.  
   
   
       6 . The edge node of  claim 5  wherein said predetermined limit does not exceed said calendar duration.  
   
   
       7 . A core node in a burst-switching network, said core node comprising: 
 at least one space switch each having a plurality of input ports, a plurality of output ports, and a burst scheduler for scheduling transfer of bursts of arbitrary sizes from said plurality of input ports to said plurality of output ports; and    a master controller operable to: 
 exchange time-locking signals with each of a plurality of edge nodes;  
 receive, from at least one edge node of said plurality of edge nodes, a stream of burst-transfer requests for bursts of arbitrary sizes; and  
 allocate each of said burst-transfer requests to one of said at least one space switch.  
   
   
   
       8 . The core node of  claim 7  wherein said master controller is further operable to communicate an indication of a burst-transfer time corresponding to said each of said burst-transfer requests to an edge node from which said each of said burst-transfer requests originated.  
   
   
       9 . The core node of  claim 8  wherein said burst scheduler comprises: 
 a first memory device for storing a calendar divided into a number of divisions where the presence in a division of an identifier of a particular input port indicates that said input port is available to transmit a new burst;    a second memory device for storing the availability time of each of said output ports;    a third memory device for storing burst-transfer requests for transfer of bursts from said input ports, each of said burst-transfer requests specifying an input port, an output port, and duration of a corresponding burst; and    a burst-scheduling kernel operable to: 
 select at least two burst-transfer requests;  
 determine a time gap between an availability time of a particular input port and an availability time of a candidate output port corresponding to each of said at least two burst-transfer requests; and  
 schedule a preferred burst-transfer request having the least time gap.  
   
   
   
       10 . A scheduler for scheduling transfer of bursts from a plurality of N input ports to a plurality of M output ports of a space switch, the scheduler comprising: 
 first means for determining a first time index at which each input port becomes unoccupied;    second means for determining a second time index at which each output port becomes unoccupied;    third means for receiving burst-transfer requests, each of said burst-transfer requests indicating an input port, an output port, and a burst duration;    fourth means for selecting a particular input port having the least first time index; and    fifth means for updating said least first time index corresponding to said particular input port.    
   
   
       11 . The scheduler of  claim 10  wherein said first means includes a first memory device for storing a calendar having a predefined calendar period and divided into a number K of divisions, each division corresponding to a time slot in said calendar period and containing an indication of a state transition in said plurality of input ports so that the presence in a division of an identifier of a particular input port indicates that said particular input port is available to transmit a new burst and the presence of a null value indicates that non of said input ports changes occupancy state during said each division.  
   
   
       12 . The scheduler of  claim 11  wherein said indication is an identifier of a specific input port belonging to said plurality of input ports, where said specific input port is scheduled to become unoccupied and available for transmitting a burst during the time slot corresponding to said indication.  
   
   
       13 . The scheduler of  claim 11  wherein said number of divisions K at least equals the number N of input ports.  
   
   
       14 . The scheduler of  claim 11  wherein said number K is substantially larger than the number N of input ports.  
   
   
       15 . The scheduler of  claim 11  wherein said second means includes a second memory device for storing an availability time of each of said M output ports.  
   
   
       16 . The scheduler of  claim 10  wherein said third means includes a third memory device for storing burst-transfer requests for transfer of bursts from said plurality of input ports, each of said burst-transfer requests specifying an input port, an output port, and a burst duration of a corresponding burst.  
   
   
       17 . The scheduler of  claim 15  wherein said fourth means includes means for sequentially reading the contents of successive divisions of said calendar until a particular index of a calendar division containing an indication of an identifier of a next-encountered input port is found, said next-encountered input port becoming a next-available input port.  
   
   
       18 . The scheduler of  claim 17  wherein, when there are no burst-transfer requests corresponding to said next-available input port, said fifth means: 
 selects an artificial burst having a duration of a pre-selected number of time slots;    adds said pre-selected number of time slots to said particular index to determine a new time index; and    writes an identifier of said next-available input port in a calendar division containing a null value and corresponding to the nearest time slot following said new time index.    
   
   
       19 . The scheduler of  claim 17  wherein, when there is one burst-transfer request corresponding to said next-available input port, said fifth means: 
 adds a burst-duration indicated in said one burst transfer request to said particular index to determine a new time index;    writes an identifier of said next-available input port in a calendar division containing a null value and corresponding to the nearest time slot following said new time index; and    writes said new time index in an entry in said second memory corresponding to an output port indicated in said one burst-transfer request.    
   
   
       20 . The scheduler of  claim 17  wherein, when there are at least two burst-transfer requests corresponding to said next-available input port, said fifth means: 
 identifies candidate output ports each corresponding to one of said at least two burst-transfer requests;    reads an availability time of each of said candidate output ports from said second memory device;    determines a time gap between the availability time of said next-available input port and said availability time of each of said candidate output ports;    selects a preferred candidate output port having the least time gap;    adds a burst-duration indicated in the burst transfer request corresponding to said preferred candidate output port to determine a new time index;    writes an identifier of said next-available input port in a calendar division containing a null value and corresponding to the nearest time slot following said new time index; and    writes said new time index in an entry in said second memory corresponding to said preferred output port.