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

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.

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, il=(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 O1+N={0,1, . . . ,N−1}, k(il,l)=1+N, k(i,l)=k((i−1)mod N,l−1) for 0≦i≦N−1 and i≠il;
• c) choosing one output j at input i, 0≦i ≦N−1, in a round-robin fashion from the set Ok(i,l) for which it has a packet to send, provided that k(i, 1)≠0 and excluding j from Ok(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 Ok(i,l) at Input i, 0≦i≦N−1 and i≠(il2)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 BMI is a bitmap for a queue that denotes destination of a head of the line packet for a queue i.

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, l1=(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 Ol+N={0,1, . . . ,N−1}, k(Il1)=l+N+1, k(mod(Il+1)mod N,I)=k(I1,l−2), and k(I,l)=k((I−1)modN,l−1) for 0≦i≦N−1 and (Il+1)mod N) and il is not equal to Il;
• c) choosing one output j at input I, 0≦I≦N−1, in a round-robin fashion from the set Ok(I,l) for which it has a packet to send, provided that k(I, 1)≠0 and excluding j from Ok(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 Ok(I,l) at Input I, 0≦I≦N−1 and I=(Il−2)mod N,to the next input (I+1)mod N, wherein Input (Il−2)mod N delays the set Ok((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 BMI is a bitmap for a queue that denotes destination of a head of the line packet for a queue i.