KR102771103B1 - Routing and scheduling method and system for FRER under time-sensitive networking - Google Patents

Abstract

A routing and scheduling method and system for FRER in citizen-centric networking are disclosed. A routing and scheduling method for FRER in citizen-centric networking according to one embodiment of the present invention may include: (a) setting an MWF constraint that ensures that a transmission schedule of a newly generated member stream is after the expected arrival time of all previous member streams; (b) performing redundant-weighted multi-path routing (RWMR) in a multi-path routing unit to obtain a fixed multi-path set; (c) generating a schedule for each flow in the order of input flows based on the multi-path set in a scheduling unit; (d) finding a flow scheduling order that maximizes the number of flows that satisfy a waiting time deadline by changing the order of the input flows in an optimization unit; (e) performing scheduling according to the flow scheduling order.

Description

Routing and scheduling method and system for FRER under time-sensitive networking

The present invention relates to a routing and scheduling method and system for FRER (Frame Replication and Elimination for Reliability) in citizen sensor networking.

The IEEE Time-Sensitive Networking Task Group is proposing a series of standards and amendments to Time-Sensitive Networking (hereinafter referred to as 'TSN' or 'Citizen Sensitive Networking') to address deterministic and real-time communication, reliability, and interoperability issues in industrial networks.

TSN can replace customized industrial networks with high quality of service (QoS) requirements, and realizes coexistence of general Ethernet-based technologies and industrial Ethernet-based technologies at low cost.

To this end, TSN provides a 'Time-Aware Shaper (hereinafter referred to as 'TAS')' mechanism through a sub-standard called IEEE 802.1Qbv, and schedules transmission schedules considering important traffic requiring deterministic communication as periodic citizen-centric traffic. TSN achieves traffic requirements (deterministic communication) by utilizing transmission schedules generated in advance.

However, no matter how well-structured the transmission schedule is, it cannot guarantee deterministic communication in unexpected situations such as link failure. Therefore, the TSN Task Group proposed a mechanism called 'Frame Replication and Elimination for Reliability (hereinafter referred to as 'FRER')' through a standard called IEEE 802.1CB to guarantee deterministic communication as much as possible and increase transmission reliability even in network failures through multi-path transmission.

Therefore, the FRER mechanism requires multi-path routing, and TSN's TAS scheduling also requires a separate scheduling technique. However, the sub-standards of TSN do not provide separate methods for these routing and TAS scheduling techniques.

Although there are various studies on single-path routing and scheduling in TSN, there is no study on routing and scheduling considering multiple paths for FRER.

FRER consumes a large amount of bandwidth by sending packets with the same content using multiple paths, and makes TAS scheduling more difficult. This ultimately increases the possibility of TAS scheduling configuration failure, so a series of composite methods are needed to apply FRER to TSN while increasing the success rate of TAS scheduling.

Korean Patent Publication No. 10-2014-0093969 (Published on July 29, 2014) - Method and device for coordinating transmission of time-sensitive data

The present invention provides a routing and scheduling method and system for FRER in citizen-centered networking, which can increase the scheduling success rate by utilizing a newly defined TAS scheduling mechanism and technique and a multi-path routing technique to efficiently apply FRER, and by applying an optimization algorithm based on a metaheuristic algorithm.

The present invention recognizes the practical limitations of the integrated technique of TAS scheduling and multi-path routing, and provides a realistic solution by separating scheduling and multi-path routing, and provides a routing and scheduling method and system for FRER in citizen-friendly networking, which can save bandwidth through member standby and forward (MWF) scheduling and ensure higher scheduling possibility in various situations.

Other objects of the present invention will be readily understood through the following description.

According to one aspect of the present invention, a routing and scheduling method for FRER in a citizen-centric network is provided, comprising the steps of: (a) setting an MWF constraint such that a transmission schedule of a newly generated member stream is after an expected arrival time of all previous member streams; (b) performing redundant-weighted multi-path routing (RWMR) in a multi-path routing unit to obtain a fixed multi-path set; (c) generating a schedule for each flow in the order of input flows based on the multi-path set in a scheduling unit; (d) finding a flow scheduling order that maximizes the number of flows that satisfy a waiting time deadline by changing the order of the input flows in an optimization unit; and (e) performing scheduling according to the flow scheduling order.

In the above step (b), P paths are generated per flow by adjusting the link weights according to the number of link overlaps, where P may be the number of requested path diversities configured by the user.

The above step (b) can increase the number of link overlaps with a probability of 1/2 for each link used in the replicated path when returning an already generated path.

In the above step (c), the scheduling unit can schedule the overlapping link if all multi-paths using the same link are scheduled up to the previous link of the overlapping link, and otherwise schedule another link.

In the above step (c), the scheduling unit schedules a variable length slot for each link, and if a schedulable slot is found at a time that satisfies the MWF constraint, scheduling is performed, and the remaining slots, excluding the used slots, can be added to the slot list as newly available slots.

In the above step (c), the scheduling unit can perform scheduling in a heuristic manner that returns the same deterministic TAS schedule result for the same input.

The above step (d) can perform optimization by applying particle swarm optimization (PSO)-based voting (PSVO).

The above PSVO can perform a solution voting (SV) process based on swap sequence PSO (SSPSO) and a solution fine-tuning (SF) process based on Simulated Annealing (SA).

The above solution voting (SV) process may include: (SV-1) generating multiple initial scheduling orders and then calculating costs, and updating the best initial scheduling order and cost for each particle; (SV-2) remembering the scheduling order with the best cost among the scheduling orders of each particle; (SV-3) performing a designated swap operation on the current solution of each particle; and (SV-4) repeating steps (SV-1) to (SV-3) until the ratio of particles with the same cost reaches a convergence criterion.

In the above (SV-3) step, the above-mentioned swap operation may include a random swap for the current scheduling order of each particle, a particle best swap that makes the current order the same as the best scheduling order if the same index value is different between the scheduling order of the current particle and the best scheduling order of the current particle, and a swarm swap that selects the best order among the scheduling orders generated by all particles up to the previous generation.

The above solution fine-tuning (SF) process can select a solution with a concentrated particle count among several best solutions with the same cost.

Meanwhile, according to another aspect of the present invention, a routing and scheduling system for FRER in citizen-centric networking is provided, comprising: a multi-path routing unit which performs redundant-weighted multi-path routing (RWMR) to obtain a fixed multi-path set; a scheduling unit which generates a schedule for each flow in the order of input flows based on the multi-path set; and an optimization unit which finds a flow scheduling order that maximizes the number of flows that satisfy a waiting time deadline by changing the order of the input flows, wherein the scheduling unit performs scheduling according to the flow scheduling order, and an MWF constraint is set as a default so that a transmission schedule of a newly generated member stream is after the expected arrival time of all previous member streams.

Other aspects, features and advantages other than those described above will become apparent from the following drawings, claims and detailed description of the invention.

According to an embodiment of the present invention, there is an effect of increasing the scheduling success rate by utilizing a newly defined TAS scheduling mechanism and technique and a multi-path routing technique to efficiently apply FRER, and applying an optimization algorithm based on a metaheuristic algorithm.

In addition, it recognizes the practical limitations of the integrated technique of TAS scheduling and multipath routing, and provides a realistic solution by separating scheduling and multipath routing, and it also has the effect of saving bandwidth through member standby and forwarding (MWF) scheduling and ensuring higher scheduling possibility in various situations.

Figure 1 is an example of implementing multiple paths from source to destination when FRER is not applied and when FRER is applied.
FIG. 2 is a block diagram of a routing and scheduling system for FRER of a citizen-centric network according to one embodiment of the present invention.
FIG. 3 is a flowchart of a routing and scheduling method for FRER in citizen networking according to one embodiment of the present invention.
Figure 4 is a conceptual diagram of a TAS at a transmission port of a switch that controls transmission gates in each queue using a gate control list (GCL).
Figure 5 is an example of a composite frame and multi-member stream managed by IEEE 802.1CB FRER.
Figure 6 is an example of constraints of MWF.
Figure 7 is a diagram showing the deadlock problem of MWF scheduling in overlapping nodes (instead of overlapping links).
Figure 8 shows the problems and solutions of RWMR's Under-Sum policy.
Figure 9 is a performance analysis graph of the ILP-based approach.
Figure 10 is a diagram showing the slot scheduling of LATS.
Figure 11 is an example of a network topology.
Figure 12 is a graph of the scheduling success rates of three scheduling algorithms in various network topologies.
Figure 13 is a graph of reliability performance in various multi-path scenarios.
Figure 14 is a scheduling performance graph of LATS and relaxedTT.
Figure 15 is a graph of the average link utilization of LATS and relaxedTT.
Figure 16 is a cost result graph for the maximum routable flow set.

The present invention can have various modifications and various embodiments, and specific embodiments are illustrated in the drawings and described in detail. However, this is not intended to limit the present invention to specific embodiments, and it should be understood that it includes all modifications, equivalents, or substitutes included in the spirit and technical scope of the present invention.

When it is said that a component is "connected" or "connected" to another component, it should be understood that it may be directly connected or connected to that other component, but that there may be other components in between. On the other hand, when it is said that a component is "directly connected" or "directly connected" to another component, it should be understood that there are no other components in between.

The terms first, second, etc. may be used to describe various components, but the components should not be limited by the terms. The terms are used only to distinguish one component from another.

The terminology used herein is for the purpose of describing particular embodiments only and is not intended to be limiting of the present invention. The singular expression includes the plural expression unless the context clearly indicates otherwise. As used herein, the terms "comprises" or "has" and the like are intended to specify the presence of a feature, number, step, operation, component, part or combination thereof described in the specification, but should be understood to not exclude in advance the possibility of the presence or addition of one or more other features, numbers, steps, operations, components, parts or combinations thereof.

In addition, it is to be understood that the components of the embodiments described with reference to each drawing are not limited to the embodiments described herein, and may be implemented to be included in other embodiments within the scope in which the technical spirit of the present invention is maintained, and that multiple embodiments may be reimplemented as one integrated embodiment even if a separate description is omitted.

In addition, when describing with reference to the attached drawings, regardless of the drawing symbols, identical components are given identical or related reference symbols, and redundant descriptions thereof are omitted. When describing the present invention, if it is determined that a detailed description of a related known technology may unnecessarily obscure the gist of the present invention, the detailed description thereof is omitted.

Additionally, terms such as “part,” “unit,” “module,” and “device” described in the specification mean a unit that processes at least one function or operation, which may be implemented by hardware, software, or a combination of hardware and software.

FIG. 1 is an example of implementing multiple paths from a source to a destination when FRER is not applied and when FRER is applied, FIG. 2 is a block diagram of a routing and scheduling system for FRER in citizen networking according to an embodiment of the present invention, and FIG. 3 is a flowchart of a routing and scheduling method for FRER in citizen networking according to an embodiment of the present invention.

FRER introduces the concept of replicated member streams for the original compound stream. FRER replicates frames at intersection switches and transmits them through multiple paths to ensure reliability against link or switch failures. It also removes unnecessary duplication by removing duplicate frames when merging cross-switches. However, the scope of IEEE 802.1CB is limited to frame replication and removal.

Completely separate paths between source and destination pairs cannot be assumed in typical network topologies. Furthermore, completely separate paths for all source-destination pairs are rare in real systems. Therefore, FRER and its supporting protocols must work even on partially separated paths that share some links. However, if the TAS scheduler does not take into account the fact that duplicate frames are removed by FRER at the cross-switch while scheduling member streams, the resulting schedule will have duplicate timeslots that are already assigned to removed frames. This reduces the schedulability and reduces the available bandwidth.

Fig. 1(a) shows an example of a multi-path configuration between a source-destination pair. The multi-path shares multiple links, and FRER handles the removal and creation of member streams at intersections, as shown in Fig. 1(b). In this case, it is necessary to perform TAS scheduling based on Fig. 1(b) rather than Fig. 1(a).

A routing and scheduling system (100) for FRER of citizen-centric networking according to one embodiment of the present invention searches for and selects multiple paths for sending member streams, and schedules TAS by considering frame duplication and removal to effectively handle an environment in which FRER operates. In order to reflect the characteristics of FRER well (MWF), a heuristic is applied to the routing part (RWMR) and routing and scheduling are separated to improve speed, and a heuristic is applied to the scheduling part (LATS) and then a metaheuristic optimization technique is applied (PSVO) to improve the routing and scheduling speed.

Most of the existing TSN studies have considered TAS scheduling for single-path routing without considering FRER. Most of the TSN studies dealing with FRER have focused on multi-path routing and have not actively considered the correlation with TAS scheduling. Even when considering both multi-path routing and TAS scheduling for FRER, there are many cases where either transmission reliability or TAS scheduling is not successfully achieved due to the high complexity caused by them and the lack of solutions for the disadvantages caused by FRER. In addition, existing studies have considered relatively simple topologies or a small number of civic traffic, making it difficult to reflect the environment of actual complex industrial networks.

In order to ensure successful TAS scheduling for complex networks while increasing transmission reliability through FRER in TSN, a hybrid approach considering multi-path techniques, scheduling techniques, and optimization specialized for FRER needs to be considered. Therefore, this embodiment relates to a system that applies a hybrid approach considering these points.

Referring to FIG. 2, the routing and scheduling system (100) for FRER of citizen-centered networking according to the present embodiment may include a multi-path routing unit (110), a scheduling unit (120), and an optimization unit (130).

In this embodiment, we recognize the practical limitations of the integrated technique of TAS scheduling and multi-path routing, and separate scheduling and multi-path routing to provide a realistic solution.

The multipath routing unit (110) performs heuristic-based multipath routing for high transmission reliability against network failures together with FRER, taking into account the IEEE 802.1CB standard (S210). The multipath routing unit (110) sets up fixed multipaths through redundancy-weighted multipath routing (RWMR).

The scheduling unit (120) performs member wait-and-forward (MWF) scheduling (S220) to effectively address the difficulty of TAS scheduling due to multi-path routing and save bandwidth.

Additionally, the scheduling unit (120) may adopt a heuristic-based Last Arrival Time Scheduler (LATS) to quickly generate a TAS schedule while considering MWF.

In this embodiment, we recognize the limitations of existing approaches and attempt to solve multi-path routing and TAS scheduling based on heuristics. However, heuristic-based approaches only provide fixed results for network configuration input values, which may reduce the possibility of successful TAS scheduling.

To solve these shortcomings, it is recognized that a heuristic-based scheduling method can also provide various scheduling results depending on the scheduling configuration order of each input traffic, and the system (100) further includes an optimization unit (130).

The optimization unit (130) can find the optimal scheduling order using simulated annealing (SA) and particle swarm optimization (PSO) (S230).

By separating multi-path routing and scheduling and performing them heuristically, while performing metaheuristic optimization, scheduling and routing can be completed (S240). In TSN, network traffic is generally classified into ST (time critical scheduled traffic), AVB (Audio/Video Traffic), and BE (Best-Effort Traffic). ST is a flow that requires low latency, low jitter, and zero congestion loss, and is generally assumed to have periodic transmission. In every period, each transmission of an ST flow must adhere to a strict deadline. Then, the scheduling of TAS involves determining the transmission time of an ST frame in each switch to satisfy the requirement. Since the ST flow is periodic, TAS scheduling is similar to the TDMA scheduling problem of determining the frame transmission time in a hyper period that includes the periods of all ST flows in the network. The generated schedule is repeated every hyper-period, and this periodic schedule is configured in the form of a GCL (Gate Control List) as shown in Fig. 4. A frame can be transmitted only if the corresponding queue is open at the time given by the GCL. Otherwise, the switch closes the transmission gate (C) to block transmission.

As illustrated in Figure 5, FRER deals with composite streams (source streams) and member streams. It sends a duplicate of each frame over multiple paths to provide preemptive seamless redundancy for industrial applications that cannot tolerate packet loss. This is similar in concept to industrial fault-tolerant protocols such as high-availability seamless redundancy (HSR) and parallel redundancy protocol (PRP) specified in IEC 62439-3. A composite stream is an end-to-end logical stream between a source and a destination, and member streams are actual substreams that are transmitted over multiple paths (not necessarily end-to-end) to ensure the reliability of the composite stream. Each member stream is transmitted over an independent path and terminates at a crossover switch where elimination is performed, and a new member stream is created when a path branches off from a switch. For example, in Figure 5, there are four member streams for one composite stream. In this case, the composite stream can withstand all single link failures and 16 out of 21 dual link failures, providing a high level of reliability.

One of the drawbacks of FRER is its redundancy. It obviously consumes more bandwidth. For example, in Fig. 5, if separate transmissions are made for all duplicate copies through all possible paths, 4.7 times more link resources are consumed than for a single shortest path flow. To mitigate this, it is essential that FRER discards already received frames to avoid retransmission of previously transmitted frames. If the TAS scheduler does not take into account the fact that duplicate frames are discarded by FRER at the cross switch while scheduling the member streams, the resulting schedule will have duplicate timeslots assigned to already discarded frames, wasting bandwidth. This problem is addressed in the present embodiment.

First, let's explain MWF, and the terms used below are summarized in Table 1.

[Table 1]

Assigning multiple schedules for the same duplicate packet on a single link wastes time and bandwidth. Therefore, in MWF, link transmission is scheduled only once for each composite stream in a flow, which avoids time/bandwidth waste when multiple paths of the composite stream overlap on that link. At the same time, to maintain the transmission reliability of FRER, at least one of the duplicate packets must be delivered on a member stream despite possible link failures, except when all paths are broken. To achieve this, the MWF principle is that the delivery schedule of a newly created member stream should be after the expected arrival times of all previous member streams.

Fig. 6 is an example to explain the constraints that MWF must satisfy. Three member streams 1, 2, and 3 are merged at switch B. Therefore, using FRER, only one frame of three replicas is forwarded and the remaining two are dropped when received. Now, assume that node failure and link failure occur in member streams 1 and 2 respectively. If the forwarding schedule of the newly created member stream (member 4) is earlier than the arrival time of the previous member stream (member 1, 2, 3), reliability cannot be obtained through member 3. Therefore, the MWF constraints can be defined as follows.

DepartureTime is the time when transmission begins on the link toward the next hop, and ArrivalTime is the time when reception is completed at the previous hop.

MWF considers the removal and creation of member streams at the cross-switches of partially separated paths. From equation (1), the transmission of a new member stream starts after all previous member streams have arrived at the merging cross-switch (except one has been removed). It should be emphasized here that the removal and creation of member streams in MWF should be considered only when multiple paths of the same composite stream overlap on the same 'link', not on 'nodes'. For example, in Fig. 7, there are two paths, A-B-D-E-G and A-C-E-F-D-G, which connect from node A to node G. The links of the two paths are completely separated, but nodes D and E are common and receive duplicate packets. Then, when nodes D and E wait for the last packet to arrive, considering member stream removal, creation and MWF, nodes D and E will be in a deadlock and will never transmit to node G. This is impossible in scheduling. Therefore, the removal and creation of member streams using MWF should be performed only when the 'links' of the multiple paths overlap.

MWF delays transmission by considering frame dropping (adding queuing delay) to eliminate time slot duplication and bandwidth waste while complying with packet delay requirements. That is, MWF does not transmit as fast as possible. This strategy is different from the conventional 'no-wait scheduling'.

Next, we will describe multipath routing and scheduling based on ILP (Integer Linear Programming) using MWF.

ILP-based approaches are widely used in routing and TAS scheduling in TSN. In this embodiment, we extend the existing ILP-based 'single-path' joint routing and scheduling method to solve the system model of 'multi-path' routing and TAS scheduling using MWF.

ILP-based multipath routing adds one more fp component, which is the pth multipath of the flow, to the existing ILP-based routing model. Therefore, the routing variables (routingVars) of the ILP model are extended as follows.

With the definition of new routing variables to configure multipaths, all ILP routing constraints must be extended as follows:

The definitions of all other constraints are identical to the single-path ILP routing model.

ILP-based TAS scheduling using MWF has three major differences from the existing ILP-based TAS scheduling. The first is that fp is added to all ILP variables to consider multi-path routing. Therefore, the expansion of scheduling variables is as follows.

TxStartVars represents the start time of transmission on the link, and TxEndVars represents the end time of transmission on the link. CollisionVars is a binary value variable used as a constraint to prevent packet collisions between different flows.

Second, based on equation (4), the ILP scheduling constraints for each variable can be extended as follows.

The above extension allows for general TAS scheduling of flows with multiple paths. Finally, to consider MWF, we need to add a new constraint on the transmission start time as follows.

According to equation (6), the transmission start times in the overlapping links are the same, which means that the transmission start time of the new member stream is after the arrival of all preceding member streams entering the starting node of the current link.

The objective function aims to create a set of maximally separated paths to increase reliability in the case of link failures. Without the objective function, any output from the ILP model can be used as a TAS schedule as long as scheduling and routing constraints are satisfied. However, the constraints so far have not considered reliability. That is, there is no constraint that aims for a set of maximally separated multipaths. Therefore, in order to maximize transmission reliability via FRER, the following objective function constructs a set of multipaths with minimal overlapping links.

The above-mentioned ILP model can provide the optimal value for the objective function within a set of constraints. However, the computational complexity in terms of time and memory may be excessively high depending on the problem's topology and flow requirements. Previous studies have already shown that joint routing and scheduling using ILP is difficult to succeed in a practical reasonable time.

In order to alleviate the complexity problem of the ILP model, Redundancy-Weighted Multipath Routing (RWMR) is applied, and RWMR is integrated with ILP-based scheduling. That is, instead of jointly solving the routing and scheduling problems using ILP, the multipath routing part (110) can first generate a multipath route by applying RWMR, and then perform ILP-based scheduling. The ILP model with fixed multipaths set through RWMR only needs to maintain scheduling constraints without routing constraints. In addition, since it has fixed paths, the number of constraints is greatly reduced from being proportional to the product of the number of links in the graph of Equation (5) to the product of the number of links in the multipaths of each flow. In other words, in the joint approach, the scheduling constraints for each flow had to be applied to all links in the topology, but since the paths are fixed, the ILP solver only needs to apply the scheduling constraints for each flow to the links in the paths. In addition, there is no longer a need to optimize the objective function. The complexity of the model is greatly reduced, as it can find solutions that only satisfy constraints.

RWMR generates P paths per flow, where P is the number of requested path diversities configured by the user. Algorithm 1 is the pseudocode of RWMR. RWMR takes a network graph (G), a flow to be routed (f), and the number of paths (P) required as input. Then RWMR tries to route the flows up to P*maxTry times until P paths are generated. For each iteration of the outer for loop, the weights of the graph links are updated. The weight of each link is initialized with the link utilization considering load balancing through the UpdateUtilizationWeight function. Then, the link weights are adjusted according to the link overlap count through the UpdateRedundancyWeight function in Algorithm 2. The link overlap count represents the number of times a link is used to generate a new path in line 6 of Algorithm 1, and is stored in the variable overlapDict.

Algorithm 2 increases the weight of link l that has been used n times by the sum of the link weights that have been used less than n times based on the value of overlapDict[l] through two inner for loops (Under-Sum policy). However, as the number of required multipaths increases, RWMR may return the same (duplicate) path that has already been generated in the previous attempt.

There are two possible reasons for this. The first is that the number of possible individual paths in the network graph is less than requested. The second is that the Under-Sum policy of RWMR cannot find a new individual path in the shortest path manner with the updated weights. The first is unavoidable. The second can be solved by modifying the weight policy.

Fig. 8(a) illustrates a case where RWMR fails to find a new path despite the existence of the Under-Sum policy. Assume that node C is the source and node B is the destination. Then, there are four possible paths (C-A-B, C-D-B, C-A-D-B, C-D-A-B) for multi-path selection. However, if we change the weights according to the Under-Sum policy, only two paths (C-A-B, C-D-B) are repeatedly generated. To solve this, when RWMR returns an already generated path, RWMR increases the overlapDict[l] value with a probability of 1/2 for each link l used in the duplicated path. Through this probabilistic approach, RWMR can solve the problem as shown in Fig. 8(b).

Solving multipath routing and TAS scheduling with MWF constraints simultaneously using ILP has a considerably high computational complexity. Therefore, in this embodiment, RWMR is used to reduce the execution time, and the multipath routing unit (110) and the scheduling unit (120) are separated.

In the following, we first investigate whether RWMR reduces the execution time of the algorithm to a practical level. In addition, we compare and analyze the reliability (path redundancy) of RWMR with the multipath routing of ILP, which guarantees the optimal results. The simulation for this analysis is performed on the National Science Foundation (NSF) network topology of single-flow type (Fig. 11 (b)). The size of each frame is 128 bytes and the transmission period is 500 us. All links are full-duplex with a bandwidth of 1 Gbps. The number of multipaths requested for each flow is 3, and a total of 10 scenarios from 10 to 100 flows are simulated. Each scenario is executed with a time limit of 1 hour.

Fig. 9(a) shows the scheduling completion times for 'ILP/Joint', which performs multi-path routing and scheduling using ILP, and 'ILP/RWMR', which performs multi-path routing via RWMR and schedules only via ILP. ILP/Joint succeeds only for the smallest scenario of 10 flows and times out for more than 20 flows (when a timeout occurs, the ILP solver stops the calculation). On the other hand, ILP/RWMR successfully performs routing and scheduling within the time limit for up to 60 flows. This means that feeding the paths generated in RWMR to the ILP scheduler provides a big advantage in terms of execution time.

Fig. 9(b) aims to compare the quality of multi-path routes generated by ILP/Joint and RWMR. It also compares with the optimal multi-path route (‘optimal’) optimized using ILP (routing only, no scheduling, within the same time constraint). The quality criterion of multi-path routing is based on Equation (7). First, in the case of ILP/Joint, there are routing results only for scenarios with 10 and 20 flows. This is because there are no more successful results due to timeout. In the 20 flow scenario, the path is not optimal because timeout occurs during the optimization process with intermediate results. On the other hand, RWMR generates routing results for all scenarios within the time constraint due to its heuristic approach. In addition, ILP/Joint generates lower quality results than RWMR for the 20 flow scenario despite pursuing the optimality due to the given time constraint. In addition, RWMR does not guarantee optimality because it is based on a heuristic approach, but it shows the same level of link redundancy when compared to the optimal result. This means that RWMR quickly generates high-quality multi-path routes in a heuristic manner.

This analysis confirms the following facts: It is almost impossible to jointly perform multi-routing and scheduling with FRER using ILP, and RWMR used in this embodiment significantly reduces the execution time while providing excellent routing quality. However, ILP/RWMR still takes a considerable amount of time for a relatively small number of flows in simple topologies. This can be seen as a fundamental limitation of ILP-based approaches.

Therefore, in this embodiment, the optimization unit (130) attempts to significantly reduce the calculation time using a heuristic method.

In order to provide faster scheduling time with fewer constraints and simplified objective function compared to the ILP-based joint routing and scheduling, ILP-based scheduling using RWMR routing is utilized. However, according to the analysis described above, the ILP-based approach is too naive to solve the TAS scheduling problem, and even if RWMR is used to reduce constraints, it cannot provide a realistic execution time. Therefore, in this embodiment, a LATS (Last Arrival Time Scheduler) that generates a TAS schedule by heuristically considering MWF together with two metaheuristic algorithms for LATS optimization is applied as the scheduling unit (120).

LATS generates a schedule for each flow in the order of input flows based on the multipath set generated by RWMR while considering MWF. In order to schedule the transmission start time on a link that is used multiple times (overlapping) in the multipath set of a composite stream, LATS needs to know the time when all corresponding multipaths reach the start node of the redundant link according to Equation (1). To do this, LATS checks whether all multipaths using the same link are scheduled up to the previous link of the overlapping link to determine whether the scheduling of the overlapping link is possible in line 13 of Algorithm 3. If all corresponding multipaths are scheduled before the overlapping link, LATS schedules the overlapping link. Otherwise, LATS moves to schedule another link. If each path is scheduled within the possible range, the path with the overlapping link is scheduled up to the link immediately before that link, and this process makes the scheduling of the overlapping link possible.

Figure 10 shows how LATS schedules variable-length slots for each link. The time (slot space) available for scheduling within a hyper-period of a TAS is limited by the time at which packets arrive at the starting node of the link. Scheduling is performed when a schedulable slot is found that satisfies the requirements (interval constraints and MWF). The slot is split into a 'used slot' and a 'remainder slot' according to the time space required by the frame, and the original slot is removed from the slot list and the remaining slot is added to the slot list as a newly available slot.

LATS is a heuristic algorithm that returns the same deterministic TAS schedule result for the same input. However, if the order of the input flows is changed, the entire schedule is changed and the number of flows that satisfy the waiting time deadline also changes. Therefore, the optimization problem of LATS is to find a flow scheduling order that maximizes the number of flows that satisfy the waiting time deadline. This is the same problem as the traveling salesman problem (TSP), which is NP-hard among permutation-based combinatorial optimization problems. Therefore, in this embodiment, to solve this problem, two metaheuristic approaches, SA (simulated-annealing)-based optimization (SAO) and particle swarm optimization (PSO)-based voting (PSVO), are applied in the optimization unit (130).

SAO applies the basic simulated annealing strategy to LATS as shown in Algorithm 4. The process is as follows.

Step 1: Calculate the cost based on the input order.

Step 2: Swap the scheduling order of the two flows.

Step 3: If the swapped outcome returns a worse cost, then probabilistically restore the previous order.

Step 4: Repeat steps 2 and 3 until all flows meet their waiting time deadlines.

In general, the quality or success rate of the TAS scheduling result can be expressed using a cost function such as the number of flows that meet the delay time deadline. However, there are two problems with this simple cost policy. First, the total number of transmissions depends on the flow period and the number of multipaths during the hyper-period. Second, the degree of violation of scheduling requirements of each flow can vary greatly. That is, a failed transmission schedule can be significantly or slightly overdue, which is not reflected in the cost. As a result, a cost policy that simply categorizes all transmissions of a flow as a single success/failure of the flow overly abstracts the scheduling results.

To solve this problem, we can apply the sum of the latency exceeded (SLE) as a cost policy for SAO. Algorithm 5 shows the cost policy SLE. SLE sums the latency exceeded during multiple transmissions of a flow (line 8). This allows SLE to calculate the multiple ( ) reflects the transmission results and the degree of failure for each transmission.

In this embodiment, the optimization unit (130) uses PSVO to improve two possible shortcomings of SAO. First, the performance can be greatly affected by the initial solution. SAO performs a flow scheduling order swap for only one permutation of the current solution in each iteration. As a result, if the initial solution is far from the optimal solution, SAO may have difficulty finding the optimal solution, i.e., a long execution time, and may fall into a local optimum (the optimal solution is when SLE returns 0, otherwise TAS scheduling fails).

The second drawback of SAO is that it must compute the cost through LATS for every swap. In general, metaheuristic algorithms that search for nearby neighbors through swap operations have a performance tradeoff with the swap size. A large swap size is more likely to reach a good solution with a relatively small number of swaps, but it is difficult to reach the global optimum due to a large step size. On the other hand, a small swap size is more likely to reach the global optimum with a refined search, but it has the disadvantage of having to perform a large number of swap operations. Therefore, the swap size should be adjusted according to the type of problem. Given this, it seems reasonable to adopt a small swap size for a more detailed exploration of the solution space for TAS schedule optimization, where the cost should converge to zero. However, SAO must compute the cost through LATS for every swap, so it needs to run LATS multiple times for optimization. LATS runs multiple loops, and the execution time can increase significantly depending on the number of flows and paths. As a result, SAO has to spend a long time evaluating a new solution in every iteration, which degrades the optimization performance. This could be a potential problem not only for SAO, but also for any algorithm that needs to compute the cost for every swap.

To solve these problems, PSVO is based on SSPSO (Swap-Sequence PSO). PSVO is divided into two stages. The first is SSPSO-based 'solution voting' (SV), and the second is SA-based 'solution fine-tuning' (SF). SV (lines 1-44 in Algorithm 6) performs a wide solution space search and returns the solution with the largest number of particles converged. The SV process in PSVO is as follows.

Step 1: PSVO generates multiple initial scheduling orders, then computes the cost and updates the best initial scheduling order/cost for each particle.

Step 2: PSVO remembers the scheduling order with the best (lowest) cost among the scheduling orders of each particle.

Step 3: PSVO performs multiple swap operations on the current solution of each particle.

Step 4: PSVO repeats steps 1-3 until the fraction of particles with the same cost is greater than or equal to convergenceRate.

In the third stage of the SV process, there are three swap operations in total. The first one is a random swap of the current scheduling order of each particle in line 15 of Algorithm 6. This operation randomly selects two flows like SAO and swaps their scheduling order. The second one is a pbestVelocity swap in lines 16–26. PSVO always remembers the best scheduling order of each particle. If the values of the same index are different between the current particle's scheduling order and the current particle's best scheduling order, it stores the swap operation in lines 16–21 so that the current order is the same as the best scheduling order. After storing the swap operation, it performs each swap operation with pBestProbability in lines 21–26. The third swap operation is a swarmVelocity swap. This is a swap operation towards the swarmOrder, which is the best order among the scheduling orders generated by all particles up to the previous generation (the loop over particles in line 14 means generation 1). For swarmOrder, swarmProbability, and the current scheduling order of each particle, PSVO repeats the same process as pbestVelocity swap in lines 27–37. PSVO stores the swap operation in lines 27–32 and performs swarmVelocity once the storing process is complete. In lines 33–37, it swaps with the probability of swarmProbability. With SV, PSVO generates an asymptotically good solution from several initial solutions, and cost computation via LATS in SV is performed only when a new generation of each particle is updated. As a result, PSVO considers a variety of initial solutions and does not even run LATS for all swaps in SV.

However, the final cost may not be 0 at the end of SV. For this, a fine-tuning process is performed via SF. SF is the same algorithm as SAO, and the initial solution is initialized to the best solution generated by SV. However, there may be multiple best solutions with the same cost. In this case, the solution with the most concentrated particles is selected (solution voting). However, since SV's solution is considered to be near-optimal, SF performs SAO in a cold state with the temperature set to a low value. Through this process, PSVO will solve the problems of SAO regarding initial solution dependency and excessive LATS running time.

In the following, we perform extensive simulations in various network scenarios to evaluate the proposal in terms of three aspects: schedulability (related to time/bandwidth waste), reliability (path diversity), and the impact of MWF on TAS scheduling. The system according to the present embodiment is compared with the state-of-the-art metaheuristic algorithm for joint multipath routing and TAS scheduling by Reusch et al.

The simulation settings are as follows.

We evaluate our algorithm on five distinct network topologies: Orion Crew Exploration Vehicle (CEV), National Science Foundation (NSF), USA Long Haul (ULH), Partial Mesh Topology (PMT), and ZONAL architecture. The network topologies are as illustrated in Fig. 11. All links are 1 Gbps full duplex and only 70% of the link bandwidth is used for TAS scheduling of ST traffic as recommended by the TSN standard to account for other traffic types (AVB and BE). For the ST traffic, we use three different flow types as listed in Table 3, each of which constitutes one-third of the total number of ST flows. Since each topology has different sizes, we test different numbers of flows in each topology for ‘high’ and ‘low’ traffic load scenarios as listed in Table 4, where ‘high’ is empirically chosen to be close to the maximum number of flows that can be supported. The default parameter settings of SAO and PSVO used in the simulations are listed in Table 2. Simulations are performed on a workstation with an Intel Core i7-8700 and 16 GB of memory.

[Table 2]

[Table 3]

[Table 4]

First, we evaluate the scheduling performance of three algorithms, SAO, PSVO, and REUSCH. The path diversity is set to P = 3, the scheduling timeout is set to 10 minutes, and 30 simulations are performed for each scenario. Figure 12(a) and (b) show the scheduling success rates when the traffic load is low and high, respectively. In Figure 12(a), SAO and PSVO achieve 100% success in all topologies, but REUSCH has low success rates in NSF and ZONAL, and 0% in ULH. In Figure 12(b), REUSCH fails to schedule for all five topologies, and SAO also has some difficulties in NSF and ULH topologies. In contrast, PSVO achieves 90% in ULH and 100% in all other scenarios. This is because REUSCH adopts simulated annealing for both routing and scheduling without considering MWF and fails to reach a solution within the time limit. In addition, PSVO overcomes the expected shortcomings of SAO, such as early solution dependency and frequent rescheduling for cost computation in each swap operation. These results together demonstrate that the proposed LATS with RWMR multipath routing and PSVO optimization provides robust scheduling performance while considering MWF for FRER support.

In addition, Fig. 12(c) shows the scheduling success rate for NSF topologies with various flows graphically. Similar to the previous two results, REUSCH's success rate drops off much earlier (at fewer flows) than SAO, while PSVO achieves 100% up to 450 ST flows. This result continues to highlight the advantage of the approach according to the present embodiment.

TAS scheduling using multipath routing for FRER should provide sufficient reliability against link failures. However, TAS scheduling should succeed first before that. However, as shown in Fig. 12(c), the scheduling performance of REUSCH is not good, making it difficult to compare the reliability of the final schedule. Therefore, we evaluate the reliability of the schedule after executing each algorithm for 10 minutes without waiting for the final (optimized) schedule. To evaluate the reliability according to the increase in path diversity, simulations were performed for five scenarios from a single path to five multipaths. The simulations were performed for five topologies in Fig. 11, and the total number of flows was fixed to 300.

Fig. 13 shows the average flow reliability for each multi-path scenario. The x-axis is the number of links that fail simultaneously, and we generate a total of 100 random link failures for each scenario to evaluate the average reliability (the fraction of flows that succeed in end-to-end transmission). The results show that PSVO achieves higher reliability than REUSCH in all scenarios even with the greedy routing approach. In addition, considering the results in Fig. 12(c), we can say that the reliability of REUSCH is achieved without respecting the deadline requirement of the flows. Therefore, the actual reliability of REUSCH for successful scheduling results will be much worse than the results in Fig. 13, and PSVO will show relatively larger performance gain compared to REUSCH. One interesting thing is that PSVO has good reliability even in the single-path scenario. This means that RWMR produces relatively successful load balancing results by using the utilization-based weighting policy.

The goal of MWF is to improve schedulability and reduce link utilization by eliminating time/bandwidth waste in TAS schedules when using FRER. To evaluate whether this goal is met, we compare LATS with the relaxed TT algorithm, which is based on the time-tabling (TT) algorithm. TT solves the TSN packet scheduling problem with a 'no-wait' policy. However, the no-wait policy is a stricter constraint that reduces the feasible solution space and makes it harder to find a solution. Therefore, for a fair comparison, relaxedTT relaxes the no-wait constraint only when a scheduling conflict occurs. Both algorithms are optimized with PSVO with a time limit of 10 minutes and simulations are run for a total of six scenarios. The path diversity (the number of multipaths) is varied from 3 to 5 in both topologies, NSF and CEV.

One way to improve schedulability is to perform all multipath scheduling on the same link only once, leaving room for other flow scheduling, but conversely, it may impose strong scheduling constraints, which may negatively affect schedulability. Figure 14 is plotted to verify whether LATS can improve schedulability with MWF. As intended, LATS has a higher scheduling success rate than RelaxedTT in all scenarios. Also, as the path diversity increases, the gain of LATS increases due to more resources saved by MWF. Figure 15 shows the average link utilization for six scenarios. Note that since the scheduling success rate of RelaxedTT is significantly lower than that of LATS, we compare the average link utilization of the two algorithms only in the scenarios where RelaxedTT succeeds (Figure 14). From the figure, we can see that LATS has a significantly lower average link utilization than RelaxedTT. And as the number of multipaths increases, the number of redundant links increases, which increases the link utilization advantage of LATS.

Finally, Fig. 16 shows the cost (SLE) convergence behavior for the maximum routable flow set when the path diversity is 3 in CEV and NSF topologies. Four cases are evaluated by combining two optimization strategies (SAO and PSVO) and two scheduling algorithms (LATS and relaxed TT). In the CEV scenario (Fig. 16(a)), the LATS-based approach achieves lower final cost than the relaxed TT for the same optimization strategy, respectively. The lower cost means that it is close to a successful TAS schedule. In addition, the PSVO-based approach achieves faster cost reduction and lower final cost than the SAO-based approach. The faster cost reduction means that the TAS scheduling results are smoothly approaching the optimum (successful schedule), i.e., the scheduling optimization performance of PSVO outperforms SAO. For the NSF topology in Fig. 16(b), PSVO also shows lower cost than SAO. The scheduling performance improvement (final cost) of LATS is not noticeable, but this is because there are fewer overlapping links (see link utilization results in (b) of Fig. 15) in the three-multipath scenario. When four or five multipaths are required, LATS provides greater performance improvement. In summary, the results show that LATS increases the schedulability and PSVO is a powerful scheduling optimization strategy.

Considering multiple paths for FRER can cause high network load and reduce the scheduling space, which can severely reduce the possibility of successful scheduling of TAS. In addition, the integrated scheduling and routing technique cannot provide practically successful routing and scheduling because the search space that must be searched for successful TSN configuration is huge. In this embodiment, a composite technique is applied that recognizes these problems and considers approaches to guarantee practical execution time from various aspects.

In order to minimize the network load and decrease in schedulability caused by FRER, the MWF scheduling mechanism can be used to complement the fundamental shortcomings of FRER, thereby ensuring higher schedulability in various situations.

By adopting a heuristic approach for scheduling considering multipath routing and MWF, we can provide very fast solutions regardless of the complexity of the problem.

To compensate for the shortcomings of the heuristic approach, a metaheuristic-based optimization strategy is introduced to increase the possibility of scheduling success. This strategy can provide high-quality solutions faster than existing algorithms.

In this embodiment, we recognize that the common strategy of multipath routing and TAS scheduling considering FRER in TSN is too complex, and so we separate the two problems.

It is revealed that existing methods have difficulty in dealing with the complexity of FRER and TAS scheduling, and various heuristic-based approaches can provide near-optimal transmission reliability, fast scheduling performance, and low network bandwidth utilization.

Considering two metaheuristic algorithms, we propose a scheduling optimization algorithm and solve the problem of low scheduling success rate due to fixed results, which is a shortcoming of heuristic-based approaches.

The above combined strategies can increase the practicality of FRER and ensure that TSN provides high reliability.

The above-described routing and scheduling method for FRER can also be implemented in the form of a recording medium containing computer-executable instructions, such as an application or program module executed by a computer. The computer-readable medium can be any available medium that can be accessed by a computer, and includes both volatile and nonvolatile media, removable and non-removable media. Furthermore, the computer-readable medium can include a computer storage medium. The computer storage medium includes both volatile and nonvolatile, removable and non-removable media implemented in any method or technology for storage of information, such as computer-readable instructions, data structures, program modules or other data.

The above-described routing and scheduling method for FRER can be executed by an application that is basically installed in the terminal (which may include a program included in a platform or operating system that is basically installed in the terminal), and can also be executed by an application (i.e., a program) that the user directly installs in the master terminal through an application providing server, such as an application store server, an application, or a web server related to the corresponding service. In this sense, the above-described routing and scheduling method for FRER can be implemented as an application (i.e., a program) that is basically installed in the terminal or directly installed by the user, and can be recorded on a computer-readable recording medium such as the terminal.

Although the present invention has been described above with reference to embodiments thereof, it will be understood by those skilled in the art that various modifications and changes may be made to the present invention without departing from the spirit and scope of the present invention as set forth in the claims below.

100: Routing and Scheduling System for FRER
110: Multi-path routing section
120: Scheduling Department
130: Optimization Department

Claims (12)

As a routing and scheduling method for FRER in citizen-centric networking,
(a) setting an MWF constraint such that the delivery schedule of a newly created member stream is after the expected arrival time of all previous member streams;
(b) a step of performing redundant-weighted multi-path routing (RWMR) in a multi-path routing section to obtain a fixed multi-path set;
(c) a step of generating a schedule for each flow in the order of input flows based on the multi-path set in the scheduling unit;
(d) a step of finding a flow scheduling order that maximizes the number of flows that satisfy the waiting time deadline by changing the order of the input flows in the optimization unit;
(e) A routing and scheduling method for FRER, comprising the step of performing scheduling according to the above flow scheduling sequence.
In the first paragraph,
A routing and scheduling method for FRER, characterized in that in the step (b) above, P paths are generated per flow by adjusting link weights according to the number of link overlaps, where P is the number of requested path diversities configured by the user.
In the second paragraph,
A routing and scheduling method for FRER, characterized in that the step (b) above increases the number of link overlaps with a probability of 1/2 for each link used in the replicated path when returning an already created path.
In the first paragraph,
A routing and scheduling method for FRER, characterized in that in the step (c), the scheduling unit schedules the overlapping link if all multi-paths using the same link are scheduled up to the previous link of the overlapping link, and otherwise schedules another link.
In paragraph 4,
In the above step (c), the scheduling unit schedules a variable length slot for each link,
Scheduling is performed when a schedulable slot is found that satisfies the MWF constraints.
A routing and scheduling method for FRER, characterized in that the remaining slots, excluding the used slots, are added to the slot list as newly available slots.
In paragraph 4,
A routing and scheduling method for FRER, characterized in that in the above step (c), the scheduling unit performs scheduling in a heuristic manner that returns the same deterministic TAS schedule result for the same input.
In the first paragraph,
The above step (d) is a routing and scheduling method for FRER characterized in that it performs optimization by applying particle swarm optimization (PSO)-based voting (PSVO).
In Article 7,
A routing and scheduling method for FRER, characterized in that the above PSVO performs a solution voting (SV) process based on swap sequence PSO (SSPSO) and a solution fine-tuning (SF) process based on Simulated Annealing (SA).
In Article 8,
The above solution voting (SV) process is:
(SV-1) A step of generating multiple initial scheduling orders, then calculating the cost, and updating the best initial scheduling order and cost for each particle;
(SV-2) A step of remembering the scheduling order with the best cost among the scheduling orders of each particle;
(SV-3) A step of performing a specified swap operation for the current solution of each particle;
(SV-4) A routing and scheduling method for FRER, characterized by including a step of repeating steps (SV-1) to (SV-3) until the ratio of particles having the same cost reaches a convergence criterion.
In Article 9,
In the above-mentioned (SV-3) step, the specified swap operation includes:
A routing and scheduling method for FRER, characterized by including a random swap for the current scheduling order of each particle, a particle best swap that makes the current order the same as the best scheduling order if the same index value is different between the scheduling order of the current particle and the best scheduling order of the current particle, and a swarm swap that selects the best order among the scheduling orders generated by all particles up to the previous generation.
In Article 8,
A routing and scheduling method for FRER, wherein the solution fine-tuning (SF) process selects a particle-concentrated solution among several best solutions having the same cost.
As a routing and scheduling system for FRER in citizen-centric networking,
A multipath routing section that obtains a fixed set of multipaths by performing redundant-weighted multipath routing (RWMR);
A scheduling unit that generates a schedule for each flow in the order of the input flows based on the above multi-path set; and
An optimization unit that finds a flow scheduling order that maximizes the number of flows that satisfy a waiting time deadline by changing the order of the input flows,
The above scheduling unit performs scheduling according to the above flow scheduling order,
A routing and scheduling system for FRER, characterized by a default MWF constraint that ensures that the delivery schedule of a newly created member stream is after the expected arrival times of all previous member streams.