RRGS-round-robin greedy scheduling for input/output terabit switches

Abstract

A novel protocol for scheduling of packets in high-speed cell based switches is provided. The switch is assumed to use a logical cross-bar fabric with input buffers. The scheduler may be used in optical as well as electronic switches with terabit capacity. The proposed round-robin greedy scheduling (RRGS) achieves optimal scheduling at terabit throughput, using a pipeline technique. The pipeline approach avoids the need for internal speedup of the switching fabric to achieve high utilization. A method for determining a time slot in a N×N crossbar switch for a round robin greedy scheduling protocol, comprising N logical queues corresponding to N output ports, the input for the protocol being a state of all the input-output queues, output of the protocol being a schedule, the method comprising: choosing input corresponding to i=(constant-k−1)mod N, stopping if there are no more inputs, otherwise choosing the next input in a round robin fashion determined by i=(i+1)mod N; choosing an output j such that a pair (i,j) to a set C={(i,j)| there is at least one packet from I to j}, if the pair (i,j) exists; removing i from a set of inputs and repeating the steps if the pair (i,j) does not exist; removing i from the set of inputs and j from a set of outputs; and adding the pair (i,j) to the schedule and repeating the steps.

What is claimed is:  
     
       1. A method for determining a time slot in a N×N crossbar switch for a round robin greedy scheduling protocol, comprising N logical queues at each input, corresponding to N output ports, the input for the protocol being a state of all the input-output queues, output of the protocol being a schedule, the method comprising: 
       a) choosing input corresponding to i=(constant−k−1)mod N;  
       b) stopping if there are no more inputs, otherwise choosing the next input in a round robin fashion determined by i=(i+1)mod N;  
       c) choosing an output j such that a pair (i,j) to a set C={(i,j)| there is at least one packet from i to j}, if the pair (i,j) exists;  
       d) removing i from a set of inputs and going to step b if the pair (i,j) does not exist in step c;  
       e) removing i from the set of inputs and j from a set of outputs; and  
       f) adding the pair (i,j) to the schedule and going to step b,  
       wherein N, I, j and k are natural numbers.  
     
     
       2. A method of scheduling wherein in each time slot N distinct schedules are in progress simultaneously for N distant future time slots, the method comprising; 
       a) making a specific future time slot available to input for scheduling in a round-robin fashion;  
       b) selecting an output for a kth time slot in future, by an input i;  
       c) starting a schedule for the kth time slot in future;  
       d) determining a next input (i+1) mod N and sending to the next input remaining outputs that are free to receive packets during the kth time slot,  
       wherein N, i, and j are natural numbers.  
     
     
       3. The method of  claim 2  wherein if an input i did not complete a schedule for the kth time it slot selects an output and sends a modified output set to a next input and if the input i completes a schedule for the kth time slot it does not send the output set to the next input. 
     
     
       4. The method of  claim 3  wherein an input that does not receive a modified set of outputs from a previous input starts a new schedule. 
     
     
       5. A method of pipelined round robin greedy scheduling for odd number of inputs wherein an lth time slot is completed using a process comprising: 
       a) Initializing k(0,1)=k(1,1)= . . . k(N−1,1)=0, const=N+1, wherein, k(i,l)>0 is the time slot for which input i reserves an output in lth time slot, i l =(const−N−1)mod N denotes an input that starts a new schedule in lth time slot, and k(i,l)=0 implies that the action of input i in time slot l is suppressed;  
       b) setting O 1+N ={0,1, . . . ,N−1}, k(i l ,l)=1+N, k(i,l)=k((i−1)mod N,l−1) for 0≦i≦N−1 and i≠i l ;  
       c) choosing one output j at input i, 0≦i ≦N−1, in a round-robin fashion from the set O k(i,l)  for which it has a packet to send, provided that k(i, 1)≠0 and excluding j from O k(i,l) ;  
       d) storing the address, at input i, 0≦i≦N−1, of the chosen output in its connection memory at location k(i, l)mod N and moving a head of line (HOL) packet from a corresponding receive input-output queue to separate transmit input-output queue;  
       e) forwarding the set O k(i,l)  at Input i, 0≦i≦N−1 and i≠(i l 2)mod N, to the next input (i+1)mod N;  
       f) establishing a cross bar connection between the input i 0≦i≦N−1 and output whose address is read from location (l mod(N+1)) of the input i's connection memory; and  
       g) transmitting the reserved packet at the head of the scheduled transmit input-output queue I through the switch core for each input I, 0≦I≦N−1,  
       wherein N, i, j, k are natural numbers and BM I  is a bitmap for a queue that denotes destination of a head of the line packet for a queue i.  
     
     
       6. A method of pipelined round robin greedy scheduling for even number of inputs wherein an ith time slot is completed using a process comprising: 
       a) Initializing k(0,1)=k(1,1)= . . . k(N−1,1)=0, const=N+1, wherein, k(I,l)>0 is the time slot for which input I reserves an output in lth time slot, l 1 =(const−N−1)mod N denotes an input that starts a new schedule in lth time slot, and k(I,l)=0 implies that the action of input I in time slot l is suppressed;  
       b) setting O l+N ={0,1, . . . ,N−1}, k(I l 1)=l+N+1, k(mod(I l +1)mod N,I)=k(I 1 ,l−2), and k(I,l)=k((I−1)modN,l−1) for 0≦i≦N−1 and (I l +1)mod N) and il is not equal to I l ;  
       c) choosing one output j at input I, 0≦I≦N−1, in a round-robin fashion from the set O k(I,l)  for which it has a packet to send, provided that k(I, 1)≠0 and excluding j from O k(I,l) ;  
       d) storing the address, at input I, 0≦I≦N−1, of the chosen output in its connection memory at location k(I, l)mod(N+1) and moving an HOL packet from a corresponding receive input-output queue to separate transmit input-output queue;  
       e) forwarding the set O k(I,l)  at Input I, 0≦I≦N−1 and I=(I l −2)mod N,to the next input (I+1)mod N, wherein Input (I l −2)mod N delays the set O k((il−2)mod N,l)  for one time slot before forwarding it;  
       f) establishing a cross bar connection between the input I, 0≦I≦N−1 and output whose address is read from location (I mod(N+1)) of the input I's connection memory;  
       g) transmitting the reserved packet at the head of the scheduled transmit input-output queue is transmitted through the switch core for each input I, 0≦I≦N−1,  
       wherein N, i, j, k are natural numbers and BM I  is a bitmap for a queue that denotes destination of a head of the line packet for a queue i.  
     
     
       7. A method according to  claim 5  wherein multicast scheduling is incorporated in round-robin greedy scheduling algorithm wherein multicast packets are stored in a first come first served fashion and have priority over unicast queues and steps in lth time slot further comprise: 
       h) chooses all outputs j such that jεO k(I,l) ∩BM I  at input I, 0≦I≦N−1 and transmitting HOL multicast packets the chosen outputs in the kth time slot.  
       i) serving unicast queues if O k(i,l) ∩BM i  is an empty set, otherwise excluding the chosen outputs from O k(i,l)  and BM i ;  
       j) deleting HOL multicast packets from the multicast queue If BM I  is empty,  
       wherein N, i, j, k are natural numbers and BM I  is a bitmap for a queue that denotes destination of a head of the line packet for a queue i.  
     
     
       8. A method according to  claim 6  wherein multicast scheduling is incorporated in round-robin greedy scheduling algorithm wherein multicast packets are stored in a first come first served fashion and have priority over unicast queues and steps in lth time slot further comprise: 
       h) choosing all outputs j such that jεO k(I,l) ∩BM I  at input I, 0≦I≦N−1;  
       i) transmitting HOL multicast packets the chosen outputs in the kth time slot;  
       j) serving unicast queues if O k(i,l) ∩BM i  is an empty set, otherwise excluding the chosen outputs from O k(i,l)  and BM I ;  
       k) deleting HOL multicast packets from the multicast queue If BM i  is empty,  
       wherein N, i, j, k are natural numbers and BM I  is a bitmap for a queue that denotes destination of a head of the line packet for a queue i.  
     
     
       9. An N stage pipeline system for scheduling a N×N switch where a stage i is associated with an input I, said stage i schedules transmission to an output in a future time slot, said future time slot rippling through all stages, wherein all pipeline stages corresponding to inputs are performing scheduling concurrently such that no two inputs choose a same future time slot at a same time, output slots being selected based on a round-robin fashion, wherein when an output is selected by a stage, the output is removed from a free pool of outputs such that a pipeline stage does not pick the output that has already been selected, wherein N and i are natural numbers.