Patent ID: 7206308

Claim:
A method of providing a non-blocking routing network having a primary level (M) with n primary nodes (m_ 0 , m_ 1 , . . . , m_n−1) and a secondary level (R) with N≧n secondary nodes (r_ 0 , r_ 1 , . . . , r_N−1) and an intermediate level (I) with s intermediate nodes (i_ 0 , i_ 1 , . . . i_s−1), comprising the steps of: (a) partitioning said intermediate level (I) to obtain p copies I_u_v, u=1, . . . , p; p>0 of q subsets I_v, u=constant, v=1, . . . , q; q>1 such that the relation p*q≧sqrt(n) is satisfied, wherein sqrt(n) denotes the square root of n, (b) choosing functions f_ 1 , . . . , f_q defined for said secondary nodes (r_ 0 , r_ 1 , . . . , r_N−1) of said secondary level (R) for mapping said secondary nodes (r_ 0 , r_ 1 , . . . , r_N−1) to said intermediate level (I) such that (b1) f_a, a=1 . . . , q, is an element of I_a, and such that (b2) the identity (r_y==r_z) of a first secondary node r_y with a second secondary note r_z follows from f_a(r_y)=f_a(r_z) and f_b(r_y)=f_b(r_z) for a<>b, (c) connecting each secondary node (r_ 0 , r_ 1 , . . . , r_N−1) to p*q intermediate nodes, wherein for a distinct secondary node r_d said p*q intermediate nodes are given by the mapping of the functions f_ 1 (r_d) 1 , . . . , f_ 1 (r_d) p , . . . , f_q(r_d) 1 , . . . f_q(r_d) p , wherein f_j( ) k denotes a mapping to the j-th subset I_k_j of the k-th copy I_j of said q subsets, and (d) connecting each primary node (m_ 0 , m_ 1 , . . . , m_n−1) to said s intermediate nodes (i_ 0 , i_ 1 , . . . i_s−1).