Multi-user flexible ethernet fine granularity time slot allocation method and apparatus

1 . A multi-user flexible Ethernet fine granularity time slot allocation method, comprising:

step S1: obtaining a current network state of flexible Ethernet (FlexE), comprising a total quantity of time slots, a quantity of idle time slots and positions of idle time slots in a current time slot allocation period;

step S2: obtaining a user demand, comprising a quantity of users requiring time slots to be allocated and a quantity of time slots required for each user;

step S3: allocating time slots for the users according to the current network state and the user demand, wherein the users have two selective time slot allocation schemes as follows:

step S3a: jitter minimization based time slot allocation, comprising allocating the time slots based only on an objective of global minimization of jitter of time slot allocated to all the users, without requiring a delay of the allocated time slots, and

step S3b: weighted sum of delay and jitter minimization based time slot allocation for each user in a sequence of the quantity of time slots required for the users from large to small, when most user input data in the current time slot allocation period are transmitted in the current time slot allocation period; and

step S4: performing time slot configuration by the FlexE according to a time slot allocation result of the user,

wherein said step S3a jitter minimization based time slot allocation in the step S3 further comprises:

step S31a: calculating an optimal time slot interval of each user, respectively, according to the total quantity of time slots in the current time slot allocation period and the quantity of time slots required for each user, wherein an optimal time slot interval of an user is calculated by dividing the total quantity of time slots by the quantity of time slots required for the user, and wherein opt u represents a result of a u th user;

step S32a: establishing a directed and edge-weighted graph for each user, respectively, according to the quantity of idle time slots and the positions of idle time slots in the current time slot allocation period and the optimal time slot interval of each user, wherein each node in the directed and edge-weighted graph represents one idle time slot, x represents a node, and loc(x) represents a position of the idle time slot corresponding to the node in the current time slot allocation period, and wherein a weight on a directed edge connecting two nodes is calculated as follows:

when a position loc(j) of an idle time slot corresponding to an inflow node j connected with the directed edge in the current time slot allocation period is greater than or equal to a position loc(i) of an idle time slot corresponding to an outflow node i connected with the directed edge in the current time slot allocation period, namely loc(j)≥loc(i), the weight on the directed edge is obtained by subtracting the position loc(i) of the idle time slot corresponding to the outflow node i connected with the directed edge in the current time slot allocation period and an optimal time slot interval opt u of the user from the position loc(j) of the idle time slot corresponding to the inflow node j connected with the directed edge in the current time slot allocation period, and dividing a square of an obtained subtracting result by the optimal time slot interval opt u of the user, mathematically represented by (loc(j)−loc(i)−opt u ) 2 /opt u : and

when the position loc(j) of the idle time slot corresponding to the inflow node j connected with the directed edge in the current time slot allocation period is less than the position loc(i) of the idle time slot corresponding to the outflow node i connected with the directed edge in the current time slot allocation period, namely loc(j)<loc(i), the weight on the directed edge is obtained by adding the position loc(j) of the idle time slot corresponding to the inflow node j connected with the directed edge in the current time slot allocation period to a total quantity N of time slots in the current time slot allocation period, subtracting the position loc(i) of the idle time slot corresponding to the outflow node i connected with the directed edge in the current time slot allocation period and the optimal time slot interval optu of the user, and dividing a square of an obtained subtracting result by the optimal time slot interval opt u of the user, mathematically represented by (loc(j)+N−loc(i)−opt u ) 2 /opt u ;

step S33a: establishing an integer linear programming mathematical optimization model in combination with three constraint conditions with minimizing global sum of jitter of allocated time slot as an objective, namely minimizing a sum of weights corresponding to path cycles of a definite quantity of edges in directed graphs of all users, wherein the three constraint conditions comprises:

condition (1) a quantity of directed edges flowing into a node on each directed and edge-weighted graph is equal to a quantity of directed edges flowing out of the node;

condition (2) a node in each directed and edge-weighted graph is allocated to at most one user, at most one edge flows out of the node, and meanwhile, at most one edge flows into the node; and

condition (3) a quantity of nodes allocated to the user meets a demand of the user for the quantity of time slots; and

step S34a: solving the established integer linear programming mathematical optimization model by using a branch and bound method to obtain a globally optimal time slot allocation result.

2 . The multi-user flexible Ethernet fine granularity time slot allocation method according to claim 1 , wherein said the step S3b weighted sum of delay and jitter minimization based time slot allocation for each user in a sequence of the quantity of time slots required for the users from large to small, on premise of most user input data in the current time slot allocation period being transmitted in the current time slot allocation period, comprising:

step S31b: obtaining a position of an input time slot of each user in the current time slot allocation period, and a weight factor a with a delay minimization objective and a weight factor 1−a with a jitter minimization objective;

step S32b: ordering according to the quantity of time slots required for the users from large to small, and allocating the time slots for each user in sequence according to the sequence, namely iteratively executing the following step S33b to step S39b for each user in sequence;

step S33b: calculating an optimal time slot interval of the current user u according to the total quantity of time slots in the current time slot allocation period and the quantity of time slots required for a current user u, wherein the optimal time slot interval of the current user u is calculated by dividing the total quantity of time slots by the quantity of time slots required for the current user u, wherein opt u represents a result of the u th user;

step S34b: calculating a quantity of input time slots of the current user u incapable of transmission in the current time slot allocation period, represented by ntx, wherein ntx_ini represents an initial value of ntx;

step S35b: establishing an m×m adjacent matrix Q (n) , wherein m represents the quantity of idle time slots in the current time slot allocation period, and each element

Q

i

,

j

(

n

)

 in the adjacent matrix Q (n) represents a sum of weight on a shortest path comprising n edges from nodes i to j;

step S36b: calculating a value of an adjacent matrix

Q

i

,

j

(

1

)

 as follows:

when i is equal to j, setting a corresponding value of the adjacent matrix as a null value;

when i is not equal to j, a value of ntx is 0, and a position loc(P 1 ) of a first input time slot of the current user u in the current time slot allocation period is less than or equal to a position of the node i in the current time slot allocation period, calculating a path weight, namely an element value of the adjacent matrix

Q

i

,

j

(

1

)

,

 according to a weight calculation method in case of being capable of transmission in the current time slot allocation period, and when i is not equal to j, the value of ntx is 0, and, the position loc(P 1 ) of the first input time slot of the current user u in the current time slot allocation period is greater than the position of the node i in the current time slot allocation period, that is, input and output time slots are not matched with each other, setting a corresponding element value of the adjacent matrix as a null value; and

when i is not equal to j and the value of ntx is greater than 0, calculating the path weight, namely the element value of the adjacent matrix

Q

i

,

j

(

1

)

,

 and setting ntx=ntx−1, according to the weight calculation method in case of being incapable of transmission in the current time slot allocation period by using a position loc(P k u −ntx+1 ) of a ntx th last time slot of input time slots of the current user u;

step S37b: selecting an intermediate node q, wherein a position of the intermediate node q in the current time slot allocation period is greater than the position of the node i in the current time slot allocation period, and smaller than a position of the node j in the current time slot allocation period; calculating an adjacent matrix

Q

i

,

j

(

n

)

 when a value of n is from 2 to the quantity k u of time slots required for the current user u minus 1, wherein an element of the adjacent matrix

Q

i

,

j

(

n

)

 means a minimum value of a sum of weight on a shortest path

Q

i

,

q

(

n

-

1

)

 containing (n−1) edges from the node i to the intermediate node q and a weight from the intermediate node q to the node j;

step S38b: when the value of n is the quantity k u of time slots required for the current user u, calculating the adjacent matrix

Q

i

,

i

(

n

)

 by adding

Q

i

,

q

(

n

-

1

)

⁢

and

⁢

Q

q

,

i

(

1

)

,

 wherein a minimum diagonal element of

Q

i

,

i

(

n

)

 is a minimum total weight corresponding to a shortest path directed cycle, without a loop, of passing through k u edges from the node i to return to the node i;

step S39b: finding out nodes passed through by the shortest path directed cycle, by a value of an adjacent matrix P (n) corresponding to the minimum total weight obtained in the step S38b, and allocating the time slots corresponding to the nodes passed through by the shortest path directed cycle to the user u; and

step S40b: updating the quantity and the positions of idle time slots in the current time slot allocation period.

3 . The multi-user flexible Ethernet fine granularity time slot allocation method according to claim 2 , wherein said calculating the quantity of input time slots of the current user u incapable of transmission in the current time slot allocation period in the step S34b further comprises:

step S34b1: initializing a value of the quantity of input time slots of the current user u incapable of transmission in the current time slot allocation period, where ntx=0, a value of the quantity of input time slots of the current user u capable of transmission in the current time slot allocation period, where ctx=0, and an input time slot indicator variable of the current user u, where i=1;

step S34b2: setting ntx=ntx+1 when a position of an i th last input time slot of the current user u in the current time slot allocation period is greater than a position of a (ctx+1) th last idle time slot in the current time slot allocation period; and

setting ctx=ctx+1 when the position of the i th last input time slot of the current user u in the current time slot allocation period is less than or equal to the position of the (ctx+1) th last idle time slot in the current time slot allocation period; and

step S34b3: setting i=i+1, and repeating the step S34b2 until a value of i is greater than the quantity of time slots required for the current user u.

4 . The multi-user flexible Ethernet fine granularity time slot allocation method according to claim 2 , wherein a value of the weight from the intermediate node q to the node j in the step S37b is calculated as follows:

step S37b1: when a value of ntx_ini is equal to 0 and a position of a time slot of the intermediate node q is greater than or equal to a position loc(P n ) of a time slot of an n th input of the current user u, calculating the value of the weight from the intermediate node q to the node j according to the calculation method capable of transmission in the current time slot allocation period;

when the value of ntx_ini is greater than 0 and the value of ntx is greater than 0, calculating the value of the weight from the intermediate node q to the node j according to the calculation method incapable of transmission in the current time slot allocation period by a position loc(P k u −ntx+1 ) of a ntx th last time slot of input time slots of the current user u and setting ntx=ntx−1; and

when the value of ntx_ini is greater than 0, the value of ntx is equal to 0 and the position of a time slot of the intermediate node q is greater than or equal to a position of a time slot of a (n-ntx_ini) th input of the current user u, calculating the value of the weight from the intermediate node q to the node j according to the calculation method capable of transmission in the current time slot allocation period by using a position loc(P n-ntx_ini ) of a (n-ntx_ini) th input time slot of the current user u; and

step S37b2: establishing an m×m adjacent matrix P (n) , and recording the intermediate node q passed through by the m×m adjacent matrix P (n) , wherein

P

i

,

j

(

n

)

=

q

 indicates that an n th hop from the node i to the node j passes through the node q, and values in

P

i

,

j

(

1

)

 are all null values.

5 . The multi-user flexible Ethernet fine granularity time slot allocation method according to claim 2 , wherein the weight calculation method in case of being incapable of transmission in the current time slot allocation period in the step S36b comprises:

step s101: calculating a jitter weight;

wherein x represents a node loc(x) represents a position of an idle time slot corresponding to the node in the current time slot allocation period, and a jitter weight on a directed edge connecting two nodes is calculated as follows:

when a position loc(j) of an idle time slot corresponding to an inflow node j connected with the directed edge in the current time slot allocation period is greater than or equal to a position loc(i) of an idle time slot corresponding to an outflow node i connected with the directed edge in the current time slot allocation period, namely loc(j)≥loc(i), a weight on the directed edge is obtained by subtracting the position loc(i) of the idle time slot corresponding to the outflow node i connected with the directed edge in the current time slot allocation period and an optimal time slot interval opt u of the user from the position loc(j) of the idle time slot corresponding to the inflow node j in the current time slot allocation period, dividing a square of an obtained subtracting result by the optimal time slot interval opt u of the user, and multiplying by the weight factor 1−a with the jitter minimization objective, mathematically represented by (1−a)×(loc(j)−loc(i)−opt u ) 2 /opt u ; and

when the position loc(j) of the idle time slot corresponding to the inflow node j connected with the directed edge in the current time slot allocation period is less than the position loc(i) of the idle time slot corresponding to the outflow node i connected with the directed edge in the current time slot allocation period, namely loc(j)<loc(i), the weight on the directed edge is obtained by adding the position loc(j) of the idle time slot corresponding to the inflow node j in the current time slot allocation period to a total quantity N of time slots in the current time slot allocation period, subtracting the position loc(i) of the idle time slot corresponding to the outflow node i connected with the directed edge in the current time slot allocation period and the optimal time slot interval opt u of the user, dividing a square of an obtained subtracting result by the optimal time slot interval opt u of the user, and multiplying by the weight factor 1−a with the jitter minimization objective, mathematically represented by (1−a)×(loc(j)+N−loc(i)−opt u ) 2 /opt u ;

step s102: calculating a delay weight, comprising:

adding a position of an idle time slot corresponding to a current outflow node i in the current time slot allocation period to the total quantity N of time slots in the current time slot allocation period, subtracting a position of a current input time slot of the current user u in the current time slot allocation period, and multiplying an obtained subtracting result by the weight factor a with the delay minimization objective; and

step s103: calculating a total weight, namely adding the jitter weight calculated in the step s101 and the delay weight calculated in the step s102.

6 . The multi-user flexible Ethernet fine granularity time slot allocation method according to claim 4 , wherein the weight calculation method in case of being capable of transmission in the current time slot allocation period in the step S36b and the step S37b comprises:

step s201: calculating a jitter weight;

wherein x represents a node, loc(x) represents a position of an idle time slot corresponding to the node in the current time slot allocation period, and a jitter weight on a directed edge connecting two nodes is calculated as follows:

when a position loc(j) of an idle time slot corresponding to an inflow node j connected with the directed edge in the current time slot allocation period is greater than or equal to a position loc(i) of an idle time slot corresponding to an outflow node i connected with the directed edge in the current time slot allocation period, namely loc(j)≥loc(i), a weight on the directed edge is obtained by subtracting the position loc(i) of the idle time slot corresponding to the outflow node i connected with the directed edge in the current time slot allocation period and an optimal time slot interval opt u of the user from the position loc(j) of the idle time slot corresponding to the inflow node j in the current time slot allocation period, dividing a square of an obtained subtracting result by the optimal time slot interval opt u of the user, and multiplying by a weight factor 1−a with a jitter minimization objective, mathematically represented by (1−a)×(loc(j)−loc(i)−opt u ) 2 /opt u ; and

when the position loc(j) of the idle time slot corresponding to the inflow node j connected with the directed edge in the current time slot allocation period is less than the position loc(i) of the idle time slot corresponding to the outflow node i connected with the directed edge in the current time slot allocation period, where loc(j)<loc(i), the weight on the directed edge is obtained by adding the position loc(j) of the idle time slot corresponding to the inflow node j in the current time slot allocation period to the total quantity N of time slots in the current time slot allocation period, subtracting the position loc(i) of the idle time slot corresponding to the outflow node i connected with the directed edge in the current time slot allocation period and the optimal time slot interval opt u of the user, dividing a square of an obtained subtracting result by the optimal time slot interval opt u of the user, and multiplying by the weight factor 1−a with the jitter minimization objective, mathematically represented by (1−a)×(loc(j)+N−loc(i)−opt u ) 2 /opt u ;

step s202: calculating a delay weight, comprising:

subtracting a position of a current input time slot of the current user u in the current time slot allocation period from a position of an idle time slot corresponding to a current outflow node in the current time slot allocation period, and multiplying an obtained subtracting result by a weight factor a with the delay minimization objective; and

step s203: calculating a total weight, namely adding the jitter weight calculated in the step s201 and the delay weight calculated in the step s202.

7 . A multi-user flexible Ethernet fine granularity time slot allocation apparatus, configured to implement the multi-user flexible Ethernet fine granularity time slot allocation method according to claim 1 .

8 . An electronic device, comprising:

one or more processors; and

a storage apparatus, configured to store one or more programs, wherein the one or more programs, when executed by the electronic device, cause the electronic device to implement the multi-user flexible Ethernet fine granularity time slot allocation method according to claim 1 .

9 . A computer-readable storage medium on which a program is stored, wherein the program, when executed by a processor, is configured to implement the multi-user flexible Ethernet fine granularity time slot allocation method according to claim 1 .