论文部分内容阅读
近年来,随着网络技术的不断发展,交换机的结构正在经历着巨大的变化。早期的OQ(Output-Queued,输出队列)结构:优点是能够提供最优的吞吐量和延时控制,但是带来了交换结构的内部带宽和输出队列的存储器访问速率必须是输入端口链路速率的N倍的缺点。后来的IQ(Input-Queued,输入队列)结构:优点是克服了OQ结构的缺点,不需要加速比,但是出现了HOL(Head of Line blocking,队头阻塞)的问题。由于传统的输出队列交换结构具有较差的可扩展性,所以输入队列(IQ)交换结构又重新进入了人们的视线,并且得到了越来越广泛的使用。在IQ交换机中采用VOQ (Virtual output queued,虚拟输出队列)缓存来解决HOL问题。现在越来越多的输入队列交换机结构的调度算法都会遇到时限保障的问题,所以人们需要设计好的算法来保证数据传输满足它相应的时限。这就是基于时限的输入队列分组调度的问题。由于时限保障意味着吞吐量和速度的保障,所以这个问题也一直是时分多址调度,优化网络调度和实时调度的研究热点和难点。对于带时限的输入队列分组调度问题,人们设计了不同的算法。其中一种是Birkhoff-Von Neumann算法,但是这种算法要求所有的流量拥有一个共同的时限并且不过载。后来,又提出了最早时限优先(EDF)调度,最小松驰度优先(MLF)调度等方法来解决流量具有多个时限的问题。最近,通过改进,一种基于非EDF的算法被提出,叫做基于流的迭代分组调度(FIPS)。这种算法可以产生比EDF算法更高的吞吐量。本文主要研究带时限的输入队列交换机中加权的实时调度问题。主要研究内容如下:(1)结合NPC问题的基本理论和归约的定义,给出了NPC问题的证明方法,进而证明了在一个带时限带权重的输入队列交换机实时调度中,如果有两个时限类,第一类流量不过载,总的流量过载,调度最大权重流量的问题是一个NPC问题。(2)在证明了这样的一个问题是NPC问题后,下一步就要找到一个近似算法来解决这个问题,在这里,我们选择了贪心算法。首先给出了交换机实时调度问题的贪心算法,然后根据线性规划的基本知识及交换机实时调度的一些性质,建立交换机实时调度问题的线性规划模型,对其进行性能分析,最后得出两个重要的结论:1.交换机实时调度的贪心算法是1/3-OPT的;2.贪心算法1/3-OPT的性能界是紧。(3)对贪心算法进行仿真,将得出的数据用图表进行分析,得出分析结果:1.在负荷较低的情况下,贪心算法调度的流量权值基本接近线性模型得出的权值上界值;2.被调度的流量中时限类越多,交换机实时调度问题的贪心算法性能越好。