Patent ID: 8089959
Filing Date: 2012-01-03
Classification: H04L

Abstract:
1. A method of scheduling connections between input ports and output ports of a switch with low jitter, said method comprising: (a) receiving a traffic rate matrix for the one or more connections, wherein each element of the traffic rate matrix defines a bandwidth value for the connections to be established between an input port and an output port of the switch during a scheduling period, and where the sum of all the elements of the traffic rate matrix is less than or equal to Q, and where the sum of each row j is R(j) and where the sum of each column k is C(k); (b) applying a recursive function, which accepts the traffic rate matrix as its input and recursively generates therefrom K new traffic rate matrices wherein K is an integer greater than one and wherein each of the K new traffic matrices has a sum of elements substantially equal to the Q/K, and the sum of each row j is substantially equal to R(j)/K, and the sum of each column k is substantially equal to C(k)/K, so that the sum of the K new traffic rate matrices substantially equals to the traffic rate matrix, wherein said recursive function forms from an input matrix a plurality of matrices whose sum substantially equals the input matrix; (c) decomposing each of said K new traffic rate matrices into a sequence of one or more partial or full permutations, each of said permutation representing connections between the input ports and output ports of the switch, wherein the set of permutations for each one of said K new traffic rate matrices provides each pair of input and output ports with substantially their requested bandwidth value as specified in that one of said new traffic rate matrices; (d) using the permutations resulting from the decomposing to schedule connections in the switch corresponding to the traffic rate matrix.