WO2015027687A1

WO2015027687A1 - Network switching scheduling method based on matrix decomposition

Info

Publication number: WO2015027687A1
Application number: PCT/CN2014/072067
Authority: WO
Inventors: 许渤; 张念; 杨琦; 邱昆
Original assignee: 电子科技大学
Priority date: 2013-08-30
Filing date: 2014-02-13
Publication date: 2015-03-05
Also published as: CN103475597B; CN103475597A

Abstract

Disclosed is a network switching scheduling method based on matrix decomposition. The method comprises: in a case in which a service flow is known, expanding a service matrix with the degree of m equal to 2^r(r is a positive integer greater than 1) and the order of N to an expansion matrix with the degree of 2 and the order of P equal to Nxm/2 by using an expansion algorithm; decomposing the P-order expansion matrix to obtain a P-order decomposition matrix with the degree of 1 by using a circular algorithm; compressing the P-order decomposition matrix to a P/2-roder compression matrix with the degree of 2; then, decomposing the P/2-roder compression matrix to obtain a P/2-order decomposition matrix with the degree of 1 by using the circular algorithm; repeatedly compressing and re-decomposing the decomposition matrix until P/2 is equal to N, that is, the order of the decomposition matrix is equal to that of the service matrix, and when the matrix decomposition is finished, the obtained decomposition matrix is a connecting matrix required by network switching scheduling. The present invention is applicable to a non-blocking switching network. When a service matrix with m equal to 2^r(r is a positive integer greater than 1) is decomposed, matrix decomposition can be performed by using the simple and feasible circular algorithm, so that the network switching scheduling with low complexity is implemented.

Description

TECHNICAL FIELD The present invention relates to the field of network switching scheduling technologies, and more particularly to a network switching scheduling method based on matrix decomposition. BACKGROUND OF THE INVENTION A multi-stage switching structure can provide more switching interfaces to meet a large number of user accesses, provide higher bandwidth, and satisfy user service quality, and has become the first choice for a large-capacity switching structure. The Multi-Plane and Multi-Stage (MPMS) structure, which is a special case of a multi-level switch fabric, is an extension of the intermediate module of the multi-stage switch fabric to the switching plane. Figure 1 is a schematic diagram of an MPMS exchange structure. The plane can be a single-stage space switch structure or a multi-stage switch structure. According to whether the arrival traffic is known, the exchange scheduling algorithm is divided into two different processing methods. If the arrival traffic is unknown, the schedule can be abstracted into a bipartite graph matching problem and solved using a bipartite graph matching algorithm. If the arrival traffic is known, a matrix decomposition algorithm can be used.

To better illustrate the matrix decomposition algorithm, first define several noun concepts.

Defining the degree of the matrix: The sum of the sum of the elements of each row in the matrix and the sum of the elements of each column ^ is the degree of the matrix. Suppose there is a matrix ^φ', ,

The degree of the matrix tn'x[ , is max

Definition 2: The business matrix ^„, where each element ^^', '], 0≤/,7<Nl, represents the number of services in which the input module number is connected to the output module number ', ^ represents the degree of the service matrix, ie the middle The number of modules, representing the maximum number of services that can be supported in a multi-level switch fabric; N is the number of input/output modules. It can be seen that the value of the element ^J^ ] in the service matrix can only be from 0, 1, 2. ..... ml, choose one. For

For MPMS, the intermediate level module refers to the switching plane.

Definition 3: Connection matrix, l ≤ k ≤ m, where each element [ ], 0 ≤ /, 7 < Nl, represents whether the input module has a service connected to the output module through the intermediate module, and its element value is 1 Connection, an element value of 0 means no connection. The subscript 1 indicates the degree of the connection matrix, that is, there is at most one service for each input module to each output module in each intermediate level module. The basic idea of the matrix decomposition algorithm is to perform a unified routing assignment for the service in the case of coordinating the global service arrival. Firstly, according to the global business situation that arrives, a business matrix is obtained. The goal of the matrix decomposition algorithm is to allocate a unified route to the global service once, that is, to decompose the business matrix into a sub-matrix A, H _m = + ₊ .. . + r. It can be known from Hall's theorem that in a non-blocking switching structure, the matrix decomposition algorithm must be able to decompose all sub-matrices. Non-blocking switching structures are: Single-stage Crossbar (cross-switching matrix), multi-level MPMS, Banyan (榕树网络), Bense, Clos, etc., all of which can be distributed by matrix decomposition algorithm. Taking MPMS as an example, as shown in Figure 1, the first trick of MPMS routing scheduling is to evenly deliver the services arriving at the input end to each plane. The matrix decomposition algorithm decomposes the service matrix to obtain each sub-matrix, and each sub-matrix can be used as the basis for setting the routing of each plane in the MPMS.

In the existing matrix decomposition algorithm, represented by a ring algorithm, all sub-matrices can be decomposed into the service matrix without rearrangement adjustment or backtracking, and the time complexity increases linearly with the increase of the number of ports. In the literature [S. Andresen, "The looping algorithm extended to base 2t rearrangeable switching networks," IEEE Trans. Commun. vol. COM-25, pp. 1057-1063, Oct. 1977] Andresen is the first in the re-arrangement without blocking The loop algorithm is used in the structure. The basic step is to find an unmarked element in the service matrix and mark it as 0. Secondly, find the last unmarked element in the same column and mark it as 1; then find the last unmarked element in the peer. Marked as 0, if the last unmarked element is not found at this time, reselect the unmarked elements of the other rows. The ring algorithm can process two sub-matrices at a time, that is, the ring algorithm is applicable to the business matrix with degree 2. Its specific implementation steps include:

Step 1. Initialize the elements of the service matrix [, '], Q ≤ i, j ≤ N_\ according to the arrival of the traffic. Initialize all connection matrices, l ≤ k ≤ 2, and mark each element value [ ] in the connection matrix as 0.

Step 2: In the business matrix ^ ₂ , the elements are traversed row by row from the element ^ ₂ [0, 0].

2.1) If no rows are found for all non-zero elements, the ring algorithm ends.

2.2) If the element ^^', '] is found to be non-zero value 2, then update the connection matrix and the corresponding element of the business matrix [ ] = 1, E [i,j] = \, H ₂ [ ] = 0, then Execute step 2.

2.3) If the element ^^', '] is found to be a non-zero value of 1, then update the connection matrix and the corresponding element of the business matrix [ ] = 1, [ ] = 0, continue to perform step 3. Step 3. Find the non-zero element value 1 in the row. If the element ^ ', /] is found to be a non-zero value 1, update the connection matrix and the corresponding element of the service matrix = 1, H ₂ [i,l] = 0 , Continue to step 4; otherwise, return to step 2.

Step 4: Find the non-zero element value 1 in the column/, and if the element ^ ₂ [r, /] is found to be a non-zero value 1, update the connection matrix and the corresponding element of the service matrix [^, /] = 1, H ₂ [r,l] = 0 , i = _r , return to step 3; otherwise, return to step 2.

It can be seen that the ring algorithm selects a starting point in step 2, then loops the jump execution between steps 3 and 4, and finally ends with returning to the starting point. The ring algorithm processes the business matrix ^ _{2 to} get two sub-matrices, El, H ₂ = + . The ring algorithm handles slightly different depending on whether the service arrives full or not. In the case of the full service, the sum of the elements of each row and column of the service matrix ^ ₂ is equal to the constant 2, then the whole process of the ring algorithm starts with the starting point of the ring and ends with the starting point of the ring, from step 4 Go to step 2 and start looking for the starting point of the next ring start, until the non-zero element is found in step 2 to end the ring algorithm. In the case of the non-full-fit service, the sum of the elements of each row and column of the service matrix ^ _{2 is} less than or equal to the constant 2, and can also be processed by the ring algorithm. In the loop traversal matrix, if the column (or row) from step 3 or 4 back to step 2 is not the starting column (or row), then the processing of a loop needs to be from the starting column (or row). The opposite direction begins to traverse the loop until it returns to step 2 again to begin looking for the starting point of the next loop start, until the non-zero element is not found in step 2 to end the ring algorithm. The following takes the full service matrix ^ ₂ as an example to implement the ring algorithm.

2 is a schematic diagram of the processing of the service matrix H ₂ by the ring algorithm. As shown in FIG. 2, the ring algorithm processes the service matrix in FIG. 2, and the labels "1, 2" respectively represent the two connection matrices. First, perform step 2 to find a non-zero value of 1 as the starting point of the start of the ring Start, the arrow pointing to represent the processing order, and finally returning to the starting point, a loop traversing End, and then performing step 2 to find the starting point of the next ring. As can be seen from Figure 2, since the service matrix ^ ₂ here is a full-fit matrix, it is completed in one loop traversal. After that, the non-zero elements in the matrix have been processed, so the starting point of the next ring is not found, and the ring algorithm decomposition ends.

In the large-capacity switching structure, for example, the MPMS and the multi-slot switching structure supporting multiple slots are non-blocking switching structures, which can be routed by a matrix decomposition algorithm. The statistics of the service matrix are equal to the number of planes and the number of slots. However, the ring algorithm is subject to the degree of the business matrix of 2. To overcome this limitation, a matrix decomposition strategy with a degree of business matrix greater than 2 has been studied. However, most of the matrix decomposition strategies obtained in the later research need to be backtracked or rearranged, and the algorithm is out of the ring algorithm, and the algorithm implementation complexity is too high and not implementable. Summary of the invention

The object of the present invention is to overcome the deficiencies of the prior art and provide a low-complexity matrix-based network switching scheduling method. For a service matrix with a satisfaction degree = 2 and a positive integer greater than 1, in a non-blocking switching network, The matrix is decomposed to obtain the connection matrix, which realizes network exchange scheduling.

To achieve the above object, the present invention is based on a matrix decomposition network switching scheduling method, which is characterized by:

S1: The number of input modules and output modules in the network is N. According to the arrival of traffic flow, the N-th order service matrix ^TM is obtained, where ^ represents the degree of the service matrix and satisfies the power exponent of 2, ie m = T, Is a positive integer greater than 1; each element of the service matrix ^ _m ^ ^ ', '] represents the number of services connected to the output module of the input module, the value range is 0 ≤ i ≤ Nl, 0 ≤ ' ≤ N_l _;

S2: expanding the service matrix H _m by using an extension algorithm to obtain a P-order extension matrix M _{2 of} degree ₂ , where P = Nxmll Μ ₂ [χ, ] represents an element in the extension matrix M ₂ , and the value range is 0< ≤ -l,0<7<-l;

S3: using the ring algorithm to perform matrix decomposition on the extended matrix ₂ , and decomposing to obtain two first-order decomposition matrices M ' ² , and the number of decomposition matrices = 2;

S4: Compressing a P-order decomposition matrix Mf = 1, 2, ... by a compression algorithm to obtain a P/ ² order compression matrix of degree 2"_;

S5: Using the ring algorithm again, matrix decomposition is performed on each compression matrix in each compression matrix M" to obtain 2K decomposition matrices M(' ² '^k;

S6: judging whether the order P/ ^{2 of the} decomposition matrix Mf/" is equal to the order N of the service matrix, if equal, the matrix decomposition ends, and the connection matrix of the network exchange scheduling is obtained: ^ ' If not equal, order P = P/2, K = 2K, returning to step S4.

The expansion algorithm in step S2 includes:

S2.1: traffic matrix ^ "in each row, each column corresponds to a number of all flags the number of flags ·, Lj, is initialized to 0; ₂ spreading matrix each row, each column corresponds to a counter c, C _y ^L, initializes all counters 0; initialize each element M ₂ [x, ] = 0 in the extended matrix M ₂ _;

S2.2: traversing each element of the business matrix ^j 'by row by row row by column ^J '], if ^ ^ ', '] is zero value, go to step S2.6, if „[ Ί is non-zero, Go to step S2.3;

S2.3: Let ix^ + R^j^ + Lj, judge whether the counter is equal to 2, if not,

2 2 Do nothing, if yes, mark A = +1 and update X; also judge whether the counter is equal to 2, if not, do nothing, if yes, the number of flags = +1 and update ^ Go to step S2.4 ;

S2.4: Let ₂ [ ,3] = ₂ [ ,3] + 1, update counter C

+l , C _y ^L =C _y ^L +l , H _m [i,j] = H _m [i,j]-\.

S2.5: Determine whether D', '] is 0, if not 0, repeat step S2.3; if it is 0, proceed to step S2.6;

S2.6: It is judged whether the element of the service matrix ^ traversal is completed. If no traversal is completed, the process returns to step S2.2 to traverse the next element. If the traversal is completed, the service matrix extension ends.

The specific method of the compression algorithm in step S4 is: dividing the decomposition matrix M into two rows and two columns to obtain a block matrix of the second order, and replacing each sub-matrix in the block matrix with the sub-matrix The sum of all the elements yields a ^ ² order compression matrix M ".

The network switching scheduling method based on matrix decomposition, when the traffic flow reaches a known state, the degree is = 2, and the service matrix with a positive integer greater than 1 and the order N is extended to a degree of 2. The expansion matrix of order P = Nx /2, the P-order extended matrix is decomposed by a ring algorithm to obtain a P-order decomposition matrix of degree 1, and the P-order decomposition matrix is compressed into a P/ ² order compression matrix of degree 2, again For the order compression, the ring algorithm is used to decompose the P/ ² order decomposition matrix with degree 1. The decomposition matrix is compressed and re-decomposed until ^ ² =w, that is, the decomposition matrix is the same as the order of the service matrix, then the matrix is decomposed. The decomposition matrix obtained at this time is the connection matrix required for network switching scheduling. The present invention is applicable to a non-blocking switching network, and breaks through the limitation of the ring algorithm for the service matrix degree of 2, and does not need Performing a more complex algorithm such as backtracking and rearrangement adjustment, but using a combination of a ring algorithm, a service matrix extension, and a decomposition matrix compression, so that the degree is = 2, and a business matrix of a positive integer greater than 1 can be easily implemented. The ring algorithm performs matrix decomposition to achieve low complexity network switching scheduling. DRAWINGS

1 is a schematic diagram of an MPMS switching structure;

FIG 2 is an annular processing algorithm schematic traffic matrix ^ _2;

3 is a flow chart of a specific implementation manner of a network switching scheduling method based on matrix decomposition according to the present invention;

4 is a flow chart of a specific implementation manner of a service matrix expansion algorithm. DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS The detailed description of the embodiments of the present invention will be described in the claims It is to be noted that in the following description, when a detailed description of known functions and designs may dilute the main content of the present invention, these descriptions will be omitted herein.

FIG. 3 is a flow chart of a specific implementation manner of a network switching scheduling method based on matrix decomposition according to the present invention. As shown in FIG. 3, the specific implementation steps of the present invention include:

S301: The number of input modules and output modules in the network is N. According to the arrival of traffic flow, an N-th order service matrix _{m is obtained} , wherein each element _m [ ], o ≤ ≤ N - 1, 0 ≤ _ / ≤ N - 1 represents the number of services that the input module is connected to the output module, ^ represents the degree of the service matrix, and = 2 is a positive integer greater than 1, that is, the present invention is only for a degree of = 2, which is a positive integer greater than one. Business matrix.

S302: Extending the service matrix by using an extended algorithm to obtain a P-order extended matrix of degree 2

M ₂ , P = Nxm/2, ₂ [ , 3], 0 ≤ , 3 ≤ corpse _1 is an element in the extension matrix ₂ .

4 is a flow chart of a specific implementation manner of a service matrix expansion algorithm. As shown in Figure 4, the business matrix expansion algorithm includes the following steps:

S401: traffic matrix ^ "in each row, all the mark number corresponding to a number of flags ·, Lj, initializing the column is 0; spreading matrix _per row, each column corresponds to a counter c, C _y ^L, initializes all counters to zero ; spreading matrix initializing each element M ₂ M ₂ [X,] = _0; initialize = 0 '= 0.

S402: It is judged whether the element D', '] is a zero value. If ^[] is a zero value, the process proceeds to step S410. If ^^^', '] is a non-zero value, the process proceeds to step S403. S403: ^x = i - ^R y = j - -^L Proceed to steps S404 and S406.

twenty two

S404: It is judged whether the counter is equal to 2, if not, no operation is performed, and the process directly proceeds to step S408; if yes, the process proceeds to step S405.

Γγΐ

S405: The number of flags is .= +1, and the update x = x + R _; ., proceeds to step S408.

S406: It is judged whether the counter is equal to 2, if not, no operation is performed, and the process directly proceeds to step S408; if yes, the process proceeds to step S407.

S407: The number of flags ^=^+1, the update proceeds to step S408.

S408: Let ₂ [ ,3] = ₂ [ ,3] + 1, update counter C

+l , C _y ^L =C _y ^L +\ , ,]= - 1.

S409: It is judged whether ^^', '] is 0, if it is not 0, it returns to step S403, and if it is 0, it proceeds to step S410.

S410: Determine whether '=W-1, if not, indicating that the element of the line has not been traversed, enter the step

S411; If yes, it indicates that the element of the line has been traversed, and the process proceeds to step S412.

S411: 7 = 7+1, that is, traversing the next element of the line, and returning to step S402.

S412: i = i + l, j = 0, that is, the next line is traversed, and the process proceeds to step S413.

S413: determining whether = N, if not, indicating that all elements of the service matrix have not been traversed, returning to step S402, traversing the next element; if yes, indicating that all elements of the service matrix have been traversed, then the service The matrix extension ends.

By using the service matrix expansion algorithm from step S401 to step S413, the service matrix of degree ^ can be expanded to the extension matrix M ₂ of degree ₂ .

S303: Perform a matrix decomposition on the extended matrix ₂ by using a ring algorithm, and decompose to obtain two P-order decomposition matrices M ' ² , and the number of decomposition matrices=2.

S304: compressing the ^: order decomposition matrix ^^, ^^,...,^: by using a compression algorithm to obtain a ^ ² order compression matrix M" with a degree of 2.

The specific method of the compression algorithm is as follows: The decomposition matrix M is divided into two rows and two columns to obtain a block matrix of P/ ² order, and each sub-matrix in the block matrix is replaced with the sum of all elements in the sub-matrix, P/ ^2nd order compression matrix M ". S305: Using the ring algorithm again, each of the compression matrices in the compression matrix M" is decomposed into the f matrix to obtain two decomposition matrices.

S306: Determine whether the order of the decomposition matrix is equal to the order of the service matrix. If it is equal to the end of the matrix decomposition, the connection matrix of the network exchange scheduling = ^^ ^/2, if not equal, let P = V2, = 2 return to step S304. Example

The implementation process of the present invention will be described below by taking the full service matrix H _{4 of} degree = 2 ² = 4 and order N = 8 as an example.

The service matrix A is extended by the extension algorithm proposed by the present invention, and an extension matrix M ₂ having a degree of 2 and an order p = Wx _W / ₂ = 16 is obtained. An input arrow indicates that a line is abstracted into two lines, and the output arrow also indicates that a column is abstracted into two columns.

The expansion matrix M ₂ degree is 2, which satisfies the requirements of the ring algorithm, and can be directly decomposed by a ring algorithm, and decomposed to obtain = 2 decomposition matrices.

Similarly, the compression matrix obtained by the decomposition matrix Μ ² is:

It can be seen that the two compression matrices ^^' ¹ and M ₂ ⁸ ' ² obtained by compression have a degree of 2, which is suitable for the ring algorithm. Next, the two compression matrices Μ ₂ ⁸ Ί, M ₂ ⁸ ' ² are respectively decomposed by the circular algorithm to obtain 4 decomposition matrices 83 8, 4

^, M M 1 o

- - ooooooooooooooll

Ooooooo oooooooll

At this time 4 8, the order of the business matrix is ooooooo ooooooo number ll, the matrix decomposition ends, ooooooo oooooooll

Connection matrix for network switching scheduling =

Ooooooo oooooooll

+0000000ooooooo 1 ll ^, therefore, it can be seen that the connection matrix can be successfully obtained by the present invention.

If the order of the service matrix is 4, and the order of the decomposition matrix obtained at this time is 8, it is necessary to reprocess the four decomposition matrices. The 4th-order decomposition matrix with 4 degrees is 1 is compressed into 4 4th-order compression matrices M with degree 2, and then the four compression matrices are decomposed by a ring algorithm to obtain 8 degrees of 4 degrees. Decompose the matrix to complete the matrix decomposition.

While the invention has been described with respect to the preferred embodiments of the present invention, it should be understood that These variations are obvious as long as the various changes are within the spirit and scope of the invention as defined and claimed in the appended claims, and all inventions that utilize the inventive concept are protected.

Claims

claims

1. A network switching scheduling method based on matrix decomposition, which is characterized by including the following steps: S1: The number of input modules and output modules in the network is both N. According to the arrival of business traffic, the N-order business matrix is obtained statistically _m , where, ^ represents the degree of the business matrix ^„ and satisfies the power index of 2, that is, m = 2 ^r ; each element ^ ^' of the business matrix ^„, '] represents the number of services connected to the input module to the output module', The value range is o≤ ≤Ni,o≤_/≤w_i;

S2: Use the expansion algorithm to expand the business matrix H _m to obtain a P-order expansion matrix M ₂ with degree 2, where P = Nxmll M ₂ [χ, ] represents the elements in the expansion matrix M ₂ , and the value range is 0< ≤ -l,0<7<-l;

S3: Use the ring algorithm to perform matrix decomposition on the extended matrix ₂ , and obtain two P-order decomposition matrices M ' ² . At this time, the number of decomposition matrices = 2;

S4: Use the compression algorithm to compress each P-order decomposition matrix Mf = 1, 2,... to obtain a P/ ² -order compression matrix with degree 2"_;

S5: Use the ring algorithm again to perform matrix decomposition on each compression matrix M ", and obtain 2K compression matrices M ' ^k .

S6: Determine whether the order P/ ² of the decomposition matrix Mf/" is equal to the order N of the service matrix. If it is equal, the matrix decomposition ends and the connection matrix of network switching scheduling is obtained: ^ ' If not equal, let P = P/2, K = 2K, return to step S4.

2. The network switching scheduling method according to claim 1, characterized in that the expansion algorithm in step S2 includes:

S2.1: Each row and column of the business matrix ^„ corresponds to a flag number, Lj, and initializes all flag numbers to 0; each row and column of the extended matrix ₂ corresponds to a counter c, C _y ^L , and initializes all counters is 0; initialize each element M ₂ [x, ] in the extended matrix M ₂ _;

S2.2: Traverse each element ^J '] in the business matrix ^" row by row and column by column. If ^ ^', '] is zero value, enter step S2.6. If "[Ί is non-zero value, Enter step S2.3;

S2.3: Let ix^ + R^j^ + Lj, determine whether the counter is equal to 2, if not,

2 2 No operation is performed. If yes, the flag number A = +1 and update ; S2.4: Let ₂ [ , 3] = ₂ [ , 3] + 1, update counter C

, H _m [i,j] = H _m [i,j]-\.

S2.5: Determine whether D', '] is 0. If not, repeat step S2.3; if it is 0, enter step S2.6;

S2.6: Determine whether the elements of the business matrix have been traversed. If not, return to step S2.2 to traverse the next element. If the traversal is completed, the business matrix expansion ends.

3. The network switching scheduling method according to claim 1 or 2, characterized in that the specific method of the compression algorithm in step S4 is: dividing the decomposition matrix M into two rows and two columns to obtain P/ For ^{a 2-} order block matrix, replace each sub-matrix in the block matrix with the sum of all elements in the sub-matrix to obtain a ^ ² -order compressed matrix M ".