| In recent years, with the continuous development of the network technology, the switch structure is undergoing great changes. From the early OQ (Output-Queued) structure:Its advantage is the ability to provide optimal throughput and delay control, but it requires that the rate of the internal switching fabric bandwidth and output queue of memory must be N times than the link rate of the input port. People put forward the IQ (Input-Queued) structure later:Its advantage is overcoming the shortcomings of the structure of the OQ, no speedup, but it appears HOL (Head of Line blocking) problem at the same time. Because traditional output queued switches have poor scalability, IQ structure become widely used. In the IQ structure, we use the VOQ (Virtual output queued) cache to solve the HOL problem. Now more and more scheduling algorithms of IQ switch structure encounter the problem of deadline guaranteed, so people need to design good algorithm to ensure that the data transmission to meet its corresponding deadline. This is the input queued packet scheduling problem based on the deadline. Because deadline guaranteed implies throughput and rate guarantees, they have also been the rsearch hotspots and difficulty problems in multi-periodic switches scheduling, optical network scheduling and real-time scheduling.For the scheduling problem of input queued packet based on the deadline, people design different algorithms. One of them is Birkhoff-Von Neumann algorithm. But this algorithm requires that all packets have a common deadline and the flow can’t be overload. Later, people put forward the EDF algorithm and the MLF algorithm to solve the problem that packets have different deadline. Recently, by improved, an algorithm based on the non-EDF was proposed, called the Flow-based Iterative Packet Scheduling (FIPS). This algorithm can produce higher throughput than EDF algorithm.In this paper, we mainly study the scheduling problem of input queued switches with deadlines and weight. The main research contents are as follows:(1) Combining the basic theories of NP-complete problems and the definition of reducibility, we give a method to proof the NPC problem. Combining the identification method, we proved that the in the real-time scheduling for a input-queued switch with packet deadlines and weight, if there are two deadline classes that the flow of first class is not overload, but the total flow is overload, the problem of scheduling a flow with the maximum weight is an NPC problem.(2) Since to prove such a problem is an NPC problem, then we shall find an approximate algorithm to solve this problem. In this paper, we choose the greedy algorithm. First we give a greedy algorithm of the real-time scheduling for switches. Then, we establish the linear programming models for the real-time scheduling problem of switches, which based on the basic theories of linear programming and some properties of real-time scheduling for switches. Finally we carry on the performance analysis and obtain two important theorems:1. The greedy algorithm of real-time scheduling for switches is1/3-OPT;2. The performance bound of1/3-OPT for greedy algorithm is tight.(3) We simulated the greedy algorithm and use the figures to analyze the data. Finally, we obtain two results:1. In the lower load situation, the scheduling weight of greedy algorithm is nearly equal to the upper bound of the weight obtained from the linear programming model.2. The more the deadline classes of the scheduled flow, the better the greedy algorithm performance for real-time scheduling problem. |
PDF Full Text Request