Scheduling control technology for information transmission in computer networks can be divided into three categories: congestion control, deadlock prevention and flow control; congestion control is to control the excessive number of packets in a certain part of the communication subnet, and network flow control It is a measure that uses software or hardware to control network data traffic.
The operating environment of this tutorial: Windows 10 system, DELL G3 computer.
The scheduling control technology of information transmission in computer networks can be divided into: congestion control, deadlock prevention, Flow control
Expand knowledge
Network Control System (NCS) refers to sensors, controllers and actuators passing through the network A closed-loop feedback control system is formed. At present, most research on NCS establishes system models, analyzes system stability, and provides control methods and control rules based on the existing problems and characteristics of NCS to ensure that the system has good stability and high-quality control performance. However, the performance of NCS not only depends on the design of control strategies and control laws, but is also limited by network communication and network resources. Information scheduling tries to avoid information conflicts and congestion in the network, thereby greatly improving the service performance of the network control system.
Information characteristics and information scheduling concepts in NCS
In NCS, the information transmitted by the network is mainly divided into two categories: real-time information and non-real-time information [3]. Real-time information has very strict time requirements. If a piece of information fails to work within the upper limit of the specified time, the information will be discarded and the latest information will be used. In the NCS information scheduling strategy, two types of data information are mainly scheduled: periodic information and aperiodic information. Periodic information is a kind of real-time information, which is generally required to be transmitted to the target node within the transmission cycle. Periodic information is also called time-triggered information or synchronization information. Aperiodic information refers to information such as service requests between nodes. Their occurrence moments are random. Aperiodic information is also called event-triggered information, asynchronous information or random information.
In addition, burst information cannot be ignored in NCS information scheduling. Burst information refers to some sudden or random events that cannot be predicted in advance (such as alarm signals, exception handling, etc.). Information must be processed within a certain period of time, otherwise the system may become abnormal or even paralyzed.
In network control systems, information scheduling occurs at the application layer, that is, in the process of information transfer between sensors, controllers and actuators. When a data transmission collision occurs at a node in the system network, information scheduling stipulates the node's priority sending order, sending time and time interval to avoid network conflicts.
In NCS, if all data transmission of the network control system can be completed within the task time limit, the transmission of the network control system is said to be schedulable.
Typical NCS information scheduling algorithm
The current research on information scheduling in network control systems is mainly divided into separate design of scheduling and control and Co-design of scheduling and control.
Separate design of scheduling and control
In NCS research, one type of research is aimed at communication networks and studies on improving network service quality. Information scheduling methods; another type of research is to study control methods to improve NCS performance based on certain network information scheduling methods. Therefore, information scheduling methods play a large role in improving NCS performance.
According to the real-time requirements of information, information scheduling is divided into static scheduling (also known as offline scheduling), dynamic scheduling (also known as online scheduling) and hybrid scheduling.
Static priority scheduling
There are many static scheduling algorithms at present. This article focuses on the following typical algorithms and algorithm improvements.
The scheduling priority of the Rate Monotonic Static Priority Scheduling (RateMonotonicSchedulingModel) algorithm is determined by the task cycle. It is the best static scheduling algorithm in a synchronous real-time task system where the task cycle is equal to the time limit. However, this algorithm has shortcomings such as exponential time complexity in scheduling decisions, too strict restrictions on task execution cycles, and can only handle tasks with fixed cycles. In view of the above shortcomings, Lehoczky et al. [23] proposed an RM algorithm that expands the scheduling feasibility conditions. Sha et al. [22] considered the blocking of tasks and gave the schedulable conditions of the RM algorithm in non-preemptive service mode. Ye Ming et al. [5] proposed a new real-time scheduling algorithm (HardReal-timeCommunicationScheduler, HRTCS) based on the RM algorithm. Wen Yuanbao et al. [4] proposed an improved RM algorithm for streaming media where the relationship between task cycle and scheduling priority is not fixed.
The task priority of the DeadlineMonotonicSchedulingModel strategy is determined by the task time limit. This scheduling algorithm should prevent tasks from exceeding their time limit and not being scheduled, thus affecting the real-time performance of the system. When the task cycle and time limit are the same or all periodic tasks are synchronized, the DM algorithm is the best static scheduling algorithm.
The static bandwidth scheduling algorithm based on time windows proposed by Hong et al. avoids interference and data conflicts during data transmission on the network. Hong et al. also applied this scheduling method to cyclic service NCS and NCS under CAN network.
Considering that this scheduling method is limited to periodic data in the scheduling network, Liu Luyuan et al. proposed a time window scheduling algorithm based on synchronous phases and asynchronous phases, so that non-periodic data can also use the static scheduling algorithm based on time windows.
Dynamic Priority Scheduling
In the dynamic priority scheduling algorithm, the time constraint relationship of tasks is not completely determined, and the arrival time of new tasks is unknown. Several classic dynamic priority scheduling algorithms are introduced below.
Earliestdeadlinefirstscheduling proposed by Liu and Layland. Task priority is the difference between task deadline and task execution time. This algorithm is the best dynamic scheduling algorithm for synchronous periodic task groups. Since EDF is a preemptive scheduling algorithm, switching between tasks requires a lot of overhead. Baker [12] gave the schedulability conditions of the EDF algorithm in non-preemptive service mode. Zhang Huijuan et al. [11] proposed a priority-driven real-time scheduling algorithm based on the EDF algorithm, which largely overcomes the scheduling shortcomings of the EDF algorithm in multi-processor systems. Liu Huai et al. [10] proposed a fault-tolerant scheduling algorithm based on the EDF algorithm. Zhang Qizhi et al. [7] used the non-interruptive EDF scheduling method to improve the end-to-end delay of periodic data frames. Hong Yanwei et al. [1] proposed how to determine the feasibility of real-time tasks on simple models and complex models respectively.
Leastlaxityfirst scheduling (Leastlaxityfirst) and the EDF algorithm can be regarded as the same type of scheduling algorithm. The task priority is the difference between the completion time limit and the task execution time minus the execution time of the periodic task. The LLF algorithm tries to avoid frequent waiting and execution of long-cycle tasks, and has less jitter.
Mosterrorfirst-tryoncediscard is a scheduling algorithm based on online acquisition of network-induced transmission errors and dynamic allocation of network bandwidth proposed by Walsh et al. [8].
The dynamic scheduling based on dead zones proposed by Otanez et al. [9] dynamically discards a certain ratio of data to reduce the load on the network while ensuring system performance. However, when multiple data packets that are allowed to access the network compete for network resources at the same time, this policy cannot determine the priority of data packet sending.
Dynamic scheduling based on business smoothing is Kewon and others who use business smoothing technology to control the traffic of the Ethernet network by inserting fixed-rate business smoothers and automatic Adapt the business smoother to limit the arrival rate of MAC layer data packets and ensure the boundedness of the network-induced delay, thereby improving the service quality of the network.
Priority improvement proposed by Cena et al.—Distributed priority Queuing scheduling (PP-DPQ) can ensure that the maximum interval of real-time data transmission has a definite upper bound, and non-real-time data competes fairly for network resources during transmission.
Time window-based dynamic scheduling (DynamicTimeWindow) is Raja's improvement on the time window-based static scheduling algorithm, and proposes priority cycle services and dynamic time window bandwidth allocation strategies.
Fuzzy dynamic scheduling is Bai Tao [13] and others who introduced fuzzy control theory into NCS information scheduling and used fuzzy logic based on IF2THEN rules to determine the priority of data transmission.
Hybrid Scheduling
Zuberi et al. proposed a hybrid communication scheduling (MTS) strategy for network control systems under CAN. When designing the scheduling strategy, considering the different real-time data requirements, different scheduling strategies can be adopted to improve the schedulability of network resources. The event-triggered real-time scheduling of annealing control tasks given by Tabuada et al. [27] is based on an event-triggered scheduler with feedback examples, and the conditions for how it guarantees system performance are given.
Co-design of scheduling and control
Currently, the co-design of control and scheduling has become a research hotspot and has received more and more attention. It can be roughly divided into open-loop scheduling and Feedback controls two aspects of real-time scheduling.
Open-loop scheduling
Scheduling of the sampling period and sampling time of data transmission nodes in each control loop in NCS
Hong based on "window" Concept, a scheduling algorithm is given that reduces the impact of delay and improves network utilization by scheduling sampling time, and establishes the constraint relationship between NCS control system performance and network performance. However, this algorithm is based on the scheduling of one-dimensional objects in the token ring system (tokenpassing system) and the polling system (polling system), and the type of information in the system is limited to periodic information. Kim et al. [16] proposed a sampling time scheduling algorithm suitable for multi-dimensional objects based on the same idea. Liu Luyuan et al. [17] proposed a scheduling algorithm that uses the remaining time window to schedule non-real-time data and improve network resource utilization.
For more related knowledge, please visit theFAQcolumn!
The above is the detailed content of What are the three categories of scheduling and control technologies for information transfer in computer networks?. For more information, please follow other related articles on the PHP Chinese website!