交叉点单缓存的Crossbar交换结构调度算法及性能研究

摘要

互联网(Internet)的出现、个人计算机的普及和各类微、小型化计算装置的广泛应用，对人类社会产生了巨大的冲击，极大地改变了人们的工作和生活方式。互联网的广泛应用造成了网络应用种类和数量大大增加以及用户数量呈指数规律增长的局面，进而对大容量、高速、高效的通信子网中继设备的需求急剧增加；网络应用模式的变化(B/S与P2P并存)和多媒体化的趋势使网络应用的服务质量保障问题日益严峻；网络运行环境的恶化使互联网(通信子网、端系统和网络应用系统)面临各类安全性问题的挑战，移动终端与无线通信技术的广泛应用使移动访问成为网络访问的新型模式。所有这一切都不断地挑战有30多年历史的互联网技术，特别是网络体系结构，也呼唤着下一代大容量、高速、高效的交换、服务质量可保障的网络交换设备和高性能、安全可靠、易管理和高可用性的通信子网，呼唤着高性能的新型网络应用系统。
　　本博士学位论文的研究工作以下一代互联网体系结构和技术研究为背景，以高性能交换技术为对象，研究网络节点的交换结构和交换技术。本项研究的重点是一类“输入及交叉点联合排队(Combined Input-Crosspoint Queued，CICQ)结构”，即在各交叉点设有单个信元长度缓存(对定长信元交换)或单个最大帧长缓存(对变长帧交换)的CICQ结构。CICQ是一种特殊的Crossbar交换结构，在保留Crossbar完全无阻塞的特性的基础上，它通过在交叉点(Cross Point)引入缓存，将输入和输出端口逻辑分离，从而缓解了传统基于输入排队的Crossbar结构中存在的输入和输出冲突问题，进而为引入高效、复杂度较低的分布式调度算法、改善交换结构的性能和交换服务质量保障提供有利的条件。随着大容量存储技术的发展和存储器价格的不断下降，CICQ结构越来越受到学界和业界的重视，与传统的Crossbar结构相比，它除了支持定长信元交换方式外，还能支持变长数据交换，为提供高性能的交换结构开辟了新的途径。
　　本文反映的主要研究成果涵盖与CICQ结构相关的两类数据交换技术：经典的基于定长信元(例如64字节)交换技术和迄今为止研究尚不多的变长数据交换技术。
　　在定长信元交换技术研究方面，作者首先提出了长队列优先的CICQ调度算法-LQP-RR(Long Queue Prioritized-Round Robin)，以解决典型的LQF-RR(Longest Queue First-Round Robin)算法的输入端排序操作的计算复杂度较高(平均时间复杂度下界为O(NlogN))、难于用硬件实现的问题。LQP-RR利用VOQ队列在实际调度过程中的局部变化特性来寻找较长的输入队列，在输入端进行一次比较即可达到目的，从而使计算复杂度简化为O(I)，因而易于用硬件实现。此外，通过引入辅助轮询指针配合调度，可进一步保证调度算法的公平性。LQP-RR算法的上述特点为笔者进一步提出计算复杂度低、交换结构利用率高和交换时延短的新型交换算法--“混合优化的调度算法”(Hybrid OptimizationPacket Scheduling，HOPS)奠定了基础。
　　HOPS算法以每一时槽都有尽可能多的输出端口有信元可输出为策略，提高对输出端口的利用率，从而使CICQ的总吞吐率最大。为此，通过输入、输出调度策略联动，即输入调度算法向交叉节点输出的信元时，尽量保证输出调度可输出信元端口数最大。笔者用流体模型证明：对满足强大数定律的许可输入流，HOPS的总吞吐率趋近交换结构理论转发能力的100％。仿真结果还表明：HOPS调度算法在各种许可流量模型下都能稳定运行，而且在交换结构无加速比条件下，其时延性能相对现有的算法有明显的提高。因为HOPS算法计算复杂度与LQP-RR相同的，因此容易实现。
　　本文有关变长数据交换技术的研究成果涉及变长直接交换和变长切分交换两类。在变长直接交换技术方面，本文提出一种基于单缓存CICQ交换结构的“两级流控变长帧调度”(Two-stage Flow-control for Variable-length Data，TFVD)算法。该算法除改进了现有CICQ变长数据直接交换算法的公平性外，还提高了交换吞吐率，缩短了时延。该算法的核心思想是在交换结构的两级调度过程中分别进行流量控制，并通过令牌配额(Token Quota)机制延迟长帧发送时间，直至积累足够配额位置，从而减小长帧对交换链路产生的影响。仿真结果表明该算法在保证调度公平性的同时，提高了交换系统的转发性能，在负载为98％的突发流量模型下，其时延比现有的变长帧直接交换算法MQF-RR、DRR和PP-VOQ分别缩短了11％，17％和25％。
　　在变长切分交换技术研究方面，本文提出了一种“反馈式多帧变长切分”(Multi-frame Variable-length Segmentation with Feedback，MVSF)策略。该策略采用多帧合并切分以避免单帧定长切分常见的填充开销；为了避免了现有的切分策略因交叉点存储空间限制可能出现系统某路输入调度暂时停顿的问题，交叉点缓存的状态信息的反馈被用作动态调整切分单元的大小的依据。仿真结果表明：反馈式多帧变长切分策略使CICQ的变长切分交换，在交换时延和系统总吞吐率方面均优于已有的切分策略。
　　服务质量保障机制是关系到下一代交换机/路由器性能的重要技术。本论文第五章对CICQ交换时延上下界进行了分析研究。应用于OQ结构中的WF2Q算法的性能接近通用处理器共享(Generalized Processor Sharing，GPS)模型的理想性能，笔者将WF2Q算法应用于交叉点单缓存的CICQ结构，同时作为输入调度和输出调度的算法，即WF2Q*-WF2Q。本文还导出了该算法在交叉点单缓存的CICQ结构变长数据交换的近似理想的GPS-GPS参考模型的“时延的上、下界表达式”，从而证明了采用该算法能够为CICQ提供有界时延的保证。

目录

文摘

英文文摘

第1章 绪论

1.1 研究的背景

1.2 交换结构概述

1.3 基于Crossbar的交换结构研究现状

1.3.1 Crossbar的概念

1.3.2 输出排队交换结构

1.3.3 输入排队交换结构

1.3.4 输入输出联合排队交换结构

1.3.5 交叉点带缓存的Crossbar交换结构

1.4 本论文的主要工作

第2章 基于交叉点单缓存的CICQ调度算法

2.1 引言

2.2 CICQ系统模型

2.3 一种长队列优先的低复杂度的CICQ调度算法

2.3.1 VOQ队列状态分析

2.3.2 LQP-RR调度算法

2.4 一种混合优化的CICQ交换结构调度算法

2.4.1 CICQ结构的输出端口利用率

2.4.2 HOPS算法

2.4.3 HOPS算法的稳定性分析

2.5 仿真分析

2.6 本章小结

第3章 基于两级流控的CICQ变长帧调度算法

3.1 引言

3.2 CICQ变长交换调度算法的研究

3.2.1 并行轮询算法PP-VOQ

3.2.2 最小分组配额队列优先调度算法MQF-RR

3.2.3 差额轮询算法DRR

3.3 变长帧调度的公平性

3.4 基于两级流控的CICQ变长帧调度算法

3.4.1 算法描述

3.4.2 公平性分析

3.5 仿真实验

3.6 本章小结

第4章 基于CICQ的变长帧切分策略研究

4.1 引言

4.2 传统的切分策略

4.2.1 切分原理

4.2.2 数据到达过程分析

4.2.3 稳定性分析

4.3 基于CICQ交换结构的数据帧切分策略

4.3.1 CICQ交换结构切分操作的特点

4.3.2 现有的切分策略

4.3.3 反馈式变长多帧切分策略

4.3.4 性能对比

4.4 本章小结

第5章 交叉点单缓存的CICQ性能保障研究

5.1 引言

5.2 广义处理器共享及其模拟

5.2.1 广义处理器模型

5.2.2 分组化的广义处理器共享

5.2.3 改进的分组化广义处理器共享

5.3 WF2Q算法在交叉点单缓存CICQ中的服务特性

5.4 本章小结

结论

致谢

参考文献

缩略词列表

攻读博士学位期间发表的论文及科研成果