论文部分内容阅读
互联网规模的指数增长要求路由器的线速与端口数量不断增加,而大容量的高性能路由器对现有的存储器技术以及路由器交换调度提出了极大的挑战。路由器需要新的、扩展性强的技术方案以适应不断增长的容量需求。另外,随着互联网的逐渐商用化,它必须为各种不同的应用提供服务质量保证。在高性能路由器容量迅速增加的情况下,如何提供服务质量保证是一个十分困难的问题。
本论文首先对交换结构与现有的调度算法进行了分类介绍,指出了主要问题与研究发展趋势。在此基础上,对于高性能路由器交换调度部分关键问题进行了深入研究,主要贡献如下:
第一,针对交叉开关交换结构调度问题,提出了队列长度加权服务匹配的思想。其基本思路是匹配求解基于目前易于实现的并行迭代算法,但对于每一个输入输出匹配,一次可以保持一段随着对应的虚拟输出队列长度单调递增的时间。基于这一思想,我们设计了相应算法,它不需队列长度信息的交换与比较,以极大尺寸匹配算法近似的复杂性,取得与极大权重匹配算法近似的性能,在非均匀流量模式下达到接近100%的吞吐效率。单次迭代的算法性能明显优于iSLIP、EDRRM以及EiSLIP等算法,适用于高性能输入排队路由器的应用。
第二,通过分析具有多输入队列的缓冲交叉开关交换结构在突发流量到达下的性能,给出了每个输入端口拥有单个或多个输入队列的缓冲交叉开关结构的饱和吞吐率。结果显示,对于单输入队列结构而言,随着平均突发长度的增加,饱和吞吐迅速从1下降,并收敛于0.5。随着每个输入端口输入队列数目的增加,饱和吞吐率逐渐接近于1。通过仿真试验,验证了分析模型的准确性。分析结果可以用于指导基于缓冲交叉开关的路由交换设备的优化设计。
第三,提出一种面向多播的多输入队列缓冲交叉开关体系结构。将多播调度分解为信元分派、输入调度、输出调度三个可以分布式并行执行的子问题,设计了相应的调度算法,降低了算法复杂性。实验结果表明,交叉点缓冲区容量与输入队列数量对多播性能都具有很大影响。在突发流量到达下,与单个多播输入队列结构相比,无论是采用O(1)复杂度的HA-RR-RR还是复杂度更高的调度算法,均能显著提高系统吞吐性能。
最后,基于均匀性分析,提出一种支持严格服务质量保证的缓冲交叉开关交换系统结构sBUX。在这一结构中,针对每一个输入或输出都设置一个均匀复用调度器sMUX。分析表明,每一个交叉点只需设置3个信元大小的缓冲即可在没有加速比的情况下,提供确定性的延时、均匀性等服务质量保证,而且100%带宽可以用于提供确保服务,提高了系统的可扩展性。