Joint optimization method for path selection and gate scheduling in time-sensitive networking

Patent metadata

Field	Value
Publication number	US-12562991-B2
Application number	US-202218713647-A
Country	US
Kind code	B2
Filing date	May 7, 2022
Priority date	Jan 17, 2022
Publication date	Feb 24, 2026
Grant date	Feb 24, 2026

Abstract

A joint optimization method for path selection and gate scheduling in time-sensitive networking comprises S1, a CNC finding a TSN topology, and abstracting same into a network directed graph; S2, a terminal device sending to a CUC a TSN connection request, and the CUC sending same to the CNC; S3, the CNC selecting K shortest paths as alternative paths; S4, the CNC selecting m preferred paths; S5, the CNC finding an optimal transmission path for a TT stream, and finding a proper transmission path for a non-TT stream; S6, CNC completing traversal; S7, configuring a gate control list for the optimal transmission path of each pair of terminal devices; and S8, the CNC encapsulating a computation result into a gate scheduling table, configuring the gate scheduling table to a TSN switch, and then sending a traffic transmission computation result to the TSN terminal device.

First claim

The invention claimed is:

1 . A joint optimization method for path selection and gate scheduling in time-sensitive networking (TSN), comprising:
step S1: discovering, by a centralized network configuration module (CNC), a TSN network topology, and abstracting, by the CNC, a network directed graph from the TSN network topology; step S2: transmitting, by a terminal device, a TSN connection request to a centralized user configuration module (CUC), through a user configuration protocol, and transmitting, by the CUC, the TSN connection request to the CNC via a user network interface (UNI); step S3: selecting, by the CNC in response to a path selection request, K (K≥3) shortest paths as preselected paths based on a fused path selection and gate scheduling algorithm; step S4: selecting, by the CNC, m (m≥2) preferred paths from the K preselected paths based on a path criticality η k (0≤η k ≤1); step S5: using, by the CNC, the m preferred paths as an input to a path selecting stage; to determine an optimal transmission path for TT streams between a pair of sender and receiver based on TSN stream features, link transmission costs and pheromone updating rules; storing, by the CNC, the optimal transmission path in a path information table o; and determining, by the CNC, a transmission path for non-TT streams; step S6: performing, by the CNC, a traversal process to determine whether there still exists a pair of sender and receiver for which the optimal transmission path has not yet been calculated; in case that there exists a pair of sender and receiver for which the optimal transmission path has not yet been calculated, proceeding to the step S3, wherein all calculated optimal transmission paths of TT streams between all pairs of senders to receivers are stored in the path information table ω; and in a case that there is no path between the sender and the receiver that has not yet been calculated, proceeding to step S7; step S7: using the path information table ω for the TT streams as an input and configuring a stream transmission constraint, to calculate a gate control list for each of the optimal transmission paths of all pairs of senders to receivers; and step S8: encapsulating, by the CNC, a calculated result into a gate scheduling table; configuring, by the CNC, the gate scheduling table to a TSN switch; and transmitting, by the CNC, a stream transmission calculation result to a TSN terminal device via the CUC.

2 . The joint optimization method for path selection and gate scheduling in TSN according to claim 1 , wherein the step S1 comprises:
discovering, by the CNC, the TSN network topology through a link discovery protocol LLDP, and abstracting, by the CNC, the network directed graph from the TSN network topology by using a network modeling algorithm; wherein the TSN network topology is represented as the directed graph of G=(V, E), where V represents a node set in the TSN and V≡(S∪H), S represents a TSN switch set, H represents a terminal device set, E represents an edge set being a set of binary tuples and representing all links in the TSN, wherein E≡{(BR i , BR j )|BR i , BR j ∈V, BR i ≠BR j and BR i is related with BR j }, where (BR i , BR j ) represents a link between a switch BR i and a switch BR j ; each of links (BR i , BR j )∈E is associated with a measurement value list that is represented by a tuples (b, ld), where b∈ and represents a remaining bandwidth of the (BR i , BR j ), ld∈ and represents a link delay comprising d BR i proc , d BR i prop and d BR i ,BR j prop , and ld BR i , BR j is bounded; a stream is an ordered data sequence transmitted from the sender to the receiver according to a requirements; a set of all TSN streams is represented as F; for each of the TSN streams, main parameters comprise: a transmission path R i of the TSN stream, an end-to-end delay D i of the TSN stream, a transmission period T i of the TSN stream, and a size S i of the TSN stream; and each of the TSN streams F i is represented as a quadruple F i ≡(R i , D i , T i , S i ); and a path between an i-th pair of a sender ES i and a receiver ES′ i includes n switches BR 1 , BR 2 , . . . , BR n , and is represented as R i ={ES i , BR 1 , BR 2 , . . . , BR n , ES′ i }, and a maximum length of frame is a maximum transmission unit MTU of an Ethernet.

3 . The joint optimization method for path selection and gate scheduling in TSN according to claim 1 , wherein the step S2 comprises:
transmitting, by the terminal device to the CUC through the user configuration protocol, the number K of the preselected paths, the number m of the preferred paths selected based on the path criticality η k , the maximum number N cyc of cycles of the algorithm, the maximum number N ant of ant, the total quantity Q of pheromones, the transmission period T i of the TSN stream, the size S i of the TSN stream, and the delay D i of the TSN stream, and transmitting, by the CUC, the connection request to the CNC via the user network interface UNI.

4 . The joint optimization method for path selection and gate scheduling in TSN according to claim 1 , wherein the selecting K shortest paths as preselected paths in the step S3 comprises:
sorting, by using a K-shortest path algorithm KSP, shortest paths in an ascending order for each pair of ES i , ES′ i ∈H; inputting the network directed graph G, the sender ES i , the receiver ES′ i , and the number K of the paths, and outputting a set p K of the K paths; and using the set p K of the K paths as an input for the step S4; wherein the step S3 comprises: step S31: inputting the network directed graph G, the sender ES i , the receiver ES′ i , and the number K of the preselected paths; step S32: calculating, by the CNC, a shortest path between ES i and ES′ i using the fused path selection and gate scheduling algorithm; and recording the shortest path as:

p
n

(

n
=
1

)

:

p
n

=

ES
i

→
"\[Rule]"

BR
a

→
"\[Rule]"

BR
b

→
"\[Rule]"

…

→
"\[Rule]"

BR
n

→
"\[Rule]"

ES
i

Assignees

• Univ Chongqing Posts & Telecom

Inventors

• Wei Min
• Fang Xingbin
• You Mengfei
• Huo Chengjie
• Wang Ping
• Xu Wei

Classifications

• H04L45/306 Primary

  Route determination based on the nature of the carried application · CPC title

• H04L45/24 Primary

  Multipath · CPC title

• H04L47/125 Primary

  by balancing the load, e.g. traffic engineering · CPC title

• Y02D30/00

  Reducing energy consumption in communication networks · CPC title

• H04L47/12

  Avoiding congestion; Recovering from congestion · CPC title