CN108809707A - A kind of TSN dispatching methods towards real-time application demand - Google Patents

Abstract

The invention discloses a TSN scheduling method oriented to real-time application requirements, and belongs to the technical field of industrial wireless network resource allocation. On the basis of software-defined network SDN, the present invention proposes a time-sensitive software-defined network TSSDN, which conducts global observation of all time-triggered flows and network topologies, introduces a scheduling problem into TSSDN, and proposes an integer A linear programming (ILP) formulation that assigns slots to time-triggered flows and routes them to avoid network queues while maximizing the energy utilization of the assigned slots in the network and computes their routing and transmission schedules. The present invention solves the constrained optimization problem of computing transmission schedules.

Description

A TSN Scheduling Method Oriented to Real-time Application Requirements

technical field

The invention relates to the technical field of industrial wireless network resource allocation, in particular to a TSN scheduling method oriented to real-time application requirements.

Background technique

A central feature of Industry 4.0 is networked cyber-physical systems, where physical processes are controlled by computers. Since many physical processes such as the motion control of a group of collaborative robots are highly time-sensitive, real-time communication networks are required to control these systems. To guarantee deterministic behavior of physical systems under control, real-time networks with deterministic bounded network delays and delay variations (jitter) are required. Traditionally fieldbuses have been used for this, and later with the development of Ethernet technology, which provides deterministic real-time properties for this, but the possibility of transmitting real-time and non-real-time traffic on the same medium is incompatible with each other, which is Resource scheduling needs to be performed on the network, and resource scheduling is a deterministic planning for the transmission of data packets in the network. Although IEEE 802.1qbv defines the basic scheduling mechanism, how to configure the scheduling to achieve bounded end-to-end network delay is beyond the scope of the standard.

Contents of the invention

The purpose of the present invention is to present the time-sensitive software-defined network architecture TSSDN on the basis of the software-defined network (SDN) based on the fact that the existing network technology is difficult to provide real-time guarantee, which provides time-triggered flow in the network physical system. Real-time guarantee. The scheduling problem is introduced in TSSDN and an Integer Linear Programming (ILP) formulation is proposed to allocate slots to time-triggered flows and route them to avoid network queues while maximizing the efficiency of the allocated slots in the network. Energy utilization, which solves a constrained optimization problem for computing transmission schedules.

The purpose of the present invention is achieved through the following technical solutions: a TSN scheduling method oriented to real-time application requirements, the method comprising the following steps:

Step 1) Set network environment parameters: On the basis of software-defined network SDN, establish a logical centralized architecture of time-sensitive software-defined network TSSDN, model the baseline network topology and time-triggered flow, and Topology is represented as a directed graph G≡(V,E), where V is a set of nodes, V≡(S∪H), S and H are sets of switches and hosts, respectively, E≡{(i,j)|i ,j∈V and i,j are connected by network links} represents a set of tuples of network links; express the time-triggered flow as a tuple ts _i ≡(s _i ,d _i ), where s _i ,d _i ∈ H, s _i and d _i are the source and destination of the flow respectively; the set of time slots available for spending is denoted as T≡{0,1,...,t _max }, where t _max is determined by the basic period of the network controller and The length of the time slot is determined;

Step 2) Set the input of the ILP formula: the set TS of scheduled time-triggered flows, TS≡{ts _i }; the mapping SL from flows to network links, SL≡{f _i,j }, If flow i is transmitted through link j, f _i,j = 1, otherwise 0; the mapping ST of flow to time slot, ST≡{t _i,k }, If flow i is assigned time slot k, t _i,k = 1, otherwise it is 0, assuming that each allocated time slot consumes one unit of energy; set the auxiliary variable of the ILP formula: auxiliary variable W, which represents the energy that the entire network architecture can Maximum energy upper limit reached; auxiliary variable SLT, SLT≡{m _i,j,k }, If flow i is transmitted through link j and is allocated time slot k, then _mi,j , _k = 1, otherwise 0; auxiliary variable C = (|TS|×|E|)+1;

Step 3) Formulate the ILP formula objective function:

Maximize

Step 4) Formulate constraints according to the ILP formula:

Each stream can be assigned at most one slot;

Among them, in(src(i)), out(src(i)) represent the input and output of the source host respectively, and in(dst(i)) and out(dst(i)) represent the input and output of the destination host respectively;

The path of a given flow i starts at its source host and ends at its destination host;

Multiple flows cannot be routed over a given link simultaneously during any slot;

Make sure that the ILP formula provides consistent values for the variables, i.e. for flow i, edge j and slot k, the variable m _i,j , _k can be 1 only if the variables f _i,j and t _i,k are both 1 ;

Step 5) Solving the ILP formula, assigning slots to time-triggered flows, and routing these flows to avoid network queues while maximizing the energy utilization in the network architecture where assigned slots consume energy.

Further, in the step 1), use NetworkX to create Erdo "sR'enyi (ER) model, random regular graph (RRG), Baraba'si-Albert (BA) model and Waxman model, which can evaluate the ILP formula more effectively .

Further, in the step 3), the objective function ensures that the cyclic path on the path is eliminated, the minimum path length is kept, and the number of time slots is allocated to the maximum, which ensures that the ILP formula maximizes the allocation time in the network architecture at the same time Gap energy utilization.

Further, in the step 4), various constraints fully guarantee the optimal scheduling, and if the transmission period of all flows is equal to the reference period, then the maximum number of time-triggered flows are scheduled from a given set of flows.

Further, in the step 5), use the commercial solver CPLEX from IBM to solve the ILP formula.

The beneficial effects of the present invention are: the present invention proposes an Integer Linear Programming (ILP) formula to allocate time slots to time-triggered flows and route them to avoid network queues while maximizing the allocation of time slots in the network architecture Energy utilization of consumed energy, which solves the constrained optimization problem for computing transmission schedules.

Description of drawings

Figure 1 TSSDN network architecture diagram;

Figure 2 is an effect diagram of the running time of the scheduled flow in the embodiment.

Detailed ways

The present invention will be further described below in conjunction with the accompanying drawings and specific embodiments, and the purpose and effect of the present invention will be more obvious.

First, on the basis of software-defined network SDN, a logical centralized architecture of time-sensitive software-defined network TSSDN is established, as shown in Figure 1; to model the baseline network topology and time-triggered flow, we will base The network topology is expressed as a directed graph G≡(V,E), where V is a set of nodes, V≡(S∪H), where S and H are sets of switches and hosts, E≡{(i,j) |i,j∈V and i,j are connected by network links} is a set of tuples representing network links; the time-triggered stream is expressed as a tuple ts _i ≡(s _i ,d _i ), where s _i , d _i ∈ H, s _i and d _i are the source and destination of the flow respectively; the set of time slots available for spending is denoted as T≡{0,1,...,t _max }, t _max is determined by the network controller The basic cycle and time slot length of the time are determined;

We set the input and variables of the ILP formula as follows: the network topology G≡(V,E), the set of scheduled time-triggered flows TS, TS≡{ts _i }; the mapping of flows to network links SL, SL≡{ f _i,j }, If flow i is transmitted through link j, f _i,j = 1, otherwise 0; the mapping ST of flow to time slot, ST≡{t _i,k }, If stream i is assigned time slot k, t _i,k = 1, otherwise it is 0, assuming that each assigned time slot consumes one unit of energy; set the auxiliary variable W of the ILP formula to represent the maximum that the entire network architecture can achieve Energy upper limit; auxiliary variable SLT, SLT≡{m _i,j,k }, If stream i is transmitted through link j and is allocated time slot k, _mi,j,k = 1, otherwise 0; auxiliary variable C = (|TS|×|E|)+1;

The formulation of the objective function is mainly to maximize the energy utilization rate of the energy consumed in the allocated time slots in the network architecture, then the objective function of the ILP formula is formulated as follows:

Maximize

Correspondingly, we formulate the constraints of the ILP formula as follows:

Each flow can only be allocated at most one slot, since they only carry one MTU-sized packet at a corresponding time.

Among them, in(src(i)), out(src(i)) represent the input and output of the source host respectively, and in(dst(i)) and out(dst(i)) represent the input and output of the destination host respectively;

The path for a given flow i starts at its source host and ends at its destination host (i.e., the source host has only one output link and no input link, and the destination host has an input link with no output link roads), for all other network nodes, the number of inbound links is equal to the number of outbound links.

During any time slot, multiple flows cannot be routed through a given link at the same time, this constraint ensures that each flow's entire path is reserved for flows only during its assigned time slot.

Finally, we need additional constraints to ensure that the ILP solver provides consistent values for the variables, i.e., for flow i, edge _j , and slot _k , the variable m Only _{i, j, k} can be 1.

Solve the ILP formulation to assign slots to time-triggered flows and route them to avoid network queues while maximizing the energy utilization of the energy consumed by assigned slots in the network architecture and calculate their routing and transmission schedules.

Further prove the beneficial effect of the present invention by corresponding experimental data below:

We use the commercial ILP solver CPLEX from IBM to solve our proposed ILP formulation, and we compute the transport schedules in 160 evaluation scenarios using 8 different topologies. Each scenario consists of 20-110 processes, where random source and destination hosts are scheduled in the network with 3-5 available slots, we deliberately chose a small number of slots to create a Challenging scenarios, even for less traffic. The results shown in Figure 2 show that the calculation of the time table of 100 time-triggered flows by this formula takes only about 8 seconds on average.

The present invention is not limited to the above-mentioned specific embodiments, and those skilled in the art can adopt various other specific embodiments to implement the present invention according to the content disclosed in the present invention. Therefore, any design that adopts the design structure and ideas of the present invention and makes some simple changes or changes falls within the scope of protection of the present invention.

Claims (5)

1. A TSN scheduling method facing real-time application requirements, characterized in that the method comprises the following steps: Step 1) Set network environment parameters: On the basis of software-defined network SDN, establish a logical centralized architecture of time-sensitive software-defined network TSSDN, model the baseline network topology and time-triggered flow, and Topology is represented as a directed graph G≡(V,E), where V is a set of nodes, V≡(S∪H), S and H are sets of switches and hosts, respectively, E≡{(i,j)|i ,j∈V and i,j are connected by network links} represents a set of tuples of network links; express the time-triggered flow as a tuple ts _i ≡(s _i ,d _i ), where s _i ,d _i ∈ H, s _i and d _i are the source and destination of the flow respectively; the set of time slots available for spending is denoted as T≡{0,1,...,t _max }, where t _max is determined by the basic period of the network controller and The length of the time slot is determined; Step 2) Set the input of the ILP formula: the set TS of scheduled time-triggered flows, TS≡{ts _i }; the mapping SL from flows to network links, SL≡{f _i,j }, If flow i is transmitted through link j, f _i,j = 1, otherwise 0; the mapping ST of flow to time slot, ST≡{t _i,k }, If flow i is assigned time slot k, t _i,k = 1, otherwise it is 0, assuming that each allocated time slot consumes one unit of energy; set the auxiliary variable of the ILP formula: auxiliary variable W, which represents the energy that the entire network architecture can Maximum energy upper limit reached; auxiliary variable SLT, SLT≡{m _i,j,k }, If stream i is transmitted through link j and is allocated time slot k, _mi,j,k = 1, otherwise 0; auxiliary variable C = (|TS|×|E|)+1; Step 3) Formulate the ILP formula objective function: Maximize Step 4) Formulate constraints according to the ILP formula: Each stream can be assigned at most one slot; Among them, in(src(i)), out(src(i)) represent the input and output of the source host respectively, and in(dst(i)) and out(dst(i)) represent the input and output of the destination host respectively; The path of a given flow i starts at its source host and ends at its destination host; Multiple flows cannot be routed over a given link simultaneously during any slot; Make sure that the ILP formula provides consistent values for the variables, i.e. for flow i, edge j and slot k, the variable m _i,j,k can be 1 only if the variables f _i,j and t _i,k are both 1 ; Step 5) Solving the ILP formula, assigning slots to time-triggered flows, and routing these flows to avoid network queues while maximizing the energy utilization in the network architecture where assigned slots consume energy. 2. A kind of TSN scheduling method facing real-time application requirements according to claim 1, characterized in that, in said step 1), use NetworkX to create Erdo "sR'enyi (ER) model, random regular graph (RRG) , Baraba'si-Albert (BA) model and Waxman model can evaluate the ILP formula more effectively. 3. A kind of TSN scheduling method facing real-time application requirements according to claim 1, characterized in that, in the step 3), the objective function guarantees that the cyclic path on the path is eliminated, keeps the minimum path length, and maximizes The number of slots is allocated appropriately, which ensures the ILP formulation while maximizing the energy utilization of the allocated slots in the network architecture. 4. A TSN scheduling method oriented to real-time application requirements according to claim 1, characterized in that, in the step 4), various constraints fully guarantee the best scheduling, if all traffic transmission periods are equal to the reference period , then schedule the maximum number of time-triggered streams from the given set of streams. 5. A kind of TSN scheduling method oriented to real-time application requirements according to claim 1, characterized in that, in said step 5), use commercial solver CPLEX from IBM to solve the ILP formula.