Method of providing a non-blocking routing network

A method of choosing connections for a set (Xn′) of n′ secondary nodes (x—1, . . . , x_n′) to intermediate nodes in a routing network arranged in a matrix with m_r rows and m_c columns, wherein four intermediate nodes V_c—1, . . . , V_c—4 are assigned to a c-th column of said matrix with c=0, . . . , m_c−1, and wherein three intermediate nodes H_r—1, H_r—3 are assigned to an r-th row of said matrix with r=0, . . . , m_r−1, comprising the steps of:

• determining a group (G—4) of columns of said matrix which contain four or less secondary nodes of said set (Xn′) (102),
• for each column c found to be in said group (G—4) of columns:
• assigning said four or less secondary nodes to the corresponding number of corresponding intermediate nodes V_c—1, . . . , V_c—4 of the respective column c (104), and
• marking said column c as processed thereby reducing the number of remaining secondary nodes and defining a reduced matrix (106),
• determining a group (R—3) of rows of said reduced matrix which contain three or less secondary nodes of said set (Xn′) (110),
• for each row r found to be in said group (R—3) of rows:
• assigning said three or less secondary nodes to the corresponding number of corresponding intermediate nodes H_r—1, . . . , H_r—3 of the respective row r (112), and
• marking said row r as processed thereby further reducing said reduced matrix and the number of remaining secondary nodes (114),
• obtaining said reduced matrix comprising eight or less rows and six or less columns of remaining secondary nodes that have not yet been assigned to intermediate nodes (120), and
• assigning said remaining secondary nodes to intermediate nodes according to a predefined scheme (133) (130).

An apparatus 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), said apparatus comprising:

• (a) means for 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) means for 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)=I_b(r_z) for a<>b,
• (c) means for 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) means for connecting each primary node (m—0, m—1, m_n−1) to said s intermediate nodes (i—0, i—1, i_s−1).

An apparatus for choosing connections for a set (Xn′) of n′ secondary nodes (x—1, . . . , x_n′) to intermediate nodes in a routing network arranged in a matrix with m_r rows and m_c columns, wherein four intermediate nodes V_c—1, . . . , V_c—4 are assigned to a c-th column of said matrix with c=0, . . . , m_c−1, and wherein three intermediate nodes H_r—1, H_r—3 are assigned to an r-th row of said matrix with r=0, . . . , m_r−1, said apparatus comprising:

• means for determining a group (G—4) of columns of said matrix which contain four or less secondary nodes of said set (Xn′) (102),
• for each column c found to be in said group (G—4) of columns:
• means for assigning said four or less secondary nodes to the corresponding number of corresponding intermediate nodes V_c—1, . . . , V_c—4 of the respective column c (104), and
• means for marking said column c as processed thereby reducing the number of remaining secondary nodes and defining a reduced matrix (106),
• means for determining a group (R—3) of rows of said reduced matrix which contain three or less secondary nodes of said set (Xn′) (110),
• for each row r found to be in said group (R—3) of rows:
• means for assigning said three or less secondary nodes to the corresponding number of corresponding intermediate nodes H_r—1, . . . , H_r—3 of the respective row r (112), and
• means for marking said row r as processed thereby further reducing said reduced matrix and the number of remaining secondary nodes (114),
• means for obtaining said reduced matrix comprising eight or less rows and six or less columns of remaining secondary nodes that have not yet been assigned to intermediate nodes (120), and
• means for assigning said remaining secondary nodes to intermediate nodes according to a predefined scheme (133) (130).

A combined routing network having at least a first and a second routing network, each routing network being 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) obtained by the method 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),
• said combined routing network comprising said first routing network and said second routing network having the same number of secondary nodes, and said first and second routing network being connected to each other via at least one secondary level (R).