摘要：近年来,随着网络技术的不断进展,交换机的结构正在经历着巨大的变化。早期的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.被调度的流量中时限类越多,交换机实时调度不足的贪心算法性能越好。关键词：交换结构论文输入队列论文NP完全论文时限论文分组调度论文贪心算法论文线性规划论文
摘要3-5
Abstract5-9
1 引言9-15
1.1 探讨背景及近况9-13
1.1.1 交换机结构9-10
1.1.2 输入队列交换机分组调度10-12
1.1.3 带时限的输入队列交换机实时调度12-13
1.2 论文主要工作13
1.3 论文内容组织13-15
2 带时限的输入队列交换机15-22
2.1 输入队列交换机的结构15-16
2.2 带时限的输入队列交换机16-18
2.3 带时限的输入队列交换机算法18-21
2.3.1 EDF算法18-20
2.3.2 Birkhoff-Von Neumann算法20-21
2.4 本章小结21-22
3 带时限的输入队列交换机调度不足的NP完全性22-35
3.1 NPC不足基本论述22-25
3.1.1 P与NP不足22-23
3.1.2 NPC不足23-25
3.2 NPC不足的证明策略25-26
3.3 带时限的输入队列交换机调度不足的NP完全性证明26-34
3.3.1 证明思路27
3.3.2 证明历程27-32
3.3.3 实例浅析32-34
3.4 本章小结34-35
4 交换机实时调度不足的贪心算法35-44
4.1 贪心算法的提出35-36
4.1.1 交换机实时调度不足的约束35-36
4.1.2 交换机实时调度不足的贪心算法36
4.2 线性规划(Linear Programming)36-39
4.2.1 线性规划的定义36-37
4.2.2 线性规划的标准型37-38
4.2.3 线性规划的对偶原理38-39
4.3 交换机实时调度不足的线性规划模型39-40
4.4 贪心算法的性能浅析40-42
4.5 本章小结42-44
5 算法仿真44-52
5.1 仿真环境44
5.2 仿真结果及结论44-51
5.3 本章小结51-52
6 总结与展望52-54
6.1 本论文工作总结52-53
6.2 进一步的工作53-54
本站原创