基于输入排队的调度算法

基于输入排队(IQ)调度算法的存储器带宽要求较低,因而能很好应用于高速路由器中。该文讨论了目前基于IQ的调度算法,对该领域的成果进行了较全面的总结,对当前研究的新进展进行了重点分析和比较,为进一步的研究提出了新的课题和思路。

输入排队中调度算法的研究

基于输入排队策略的路由器具有良好的可扩展性,但需要一个有效的调度算法的支持,才能保证吞吐率和延迟等性能。文章对一些典型的输入排队调度算法进行了分析,为输入排队调度算法的进一步研究提出了新的思路和方向。

VOQ输出端解复用算法及其技术实现

目前的高速交换机大都采用虚拟输出排队(VOQ)方法,并把变长分组拆成定长信元后交换。已有的关于队列组织与管理的文章都着重于讨论N×N交换结构中每个端口对应于一个实际物理端口的情况,但在实际中经常需要对端口进行复用和解复用。我们针对863“实用化综合接入系统”边缘路由器子系统的设计特点,自行提出了基于输出子端口的队列组织与解复用算法。这篇文章阐述了该算法,并给出了算法的性能分析和具体实现。

CICQ交换结构的调度算法研究

研究了基于缓冲交换结构的各种调度算法,并基于CICQ(combinedinputandcrosspoint-queued)的交换结构提出LQF_LQF算法.仿真结果说明该算法在均匀分布和突发业务源的情况下都能近似达到输出排队的时延性能.

一种简单的VOQ交换机时延确保分组调度算法

采用EDF(Earliest Deadline First)与轮询结合的方法,提出了一种简单的VOQ(Virtual Output Queueing)分组调度算法提供基于流的时延确保.VOQ队列采用EDF的策略裁决分组流的竞争,输入输出端口采用轮询方式匹配.此时VOQ中分组到达至成为头分组的时间以及分组成为头分组至传输到相应输出端口的时间,分别对应于OQ中的分组排队等待时间及服务时间.通过对所得算法详细的理论分析,给出了流时延界及流分组到达的显性关系.更为重要的是,本文的理论结果不仅为设计更为有效的算法奠定了基础,同时为判别不同流的时延要求是否冲突提供了一种新的直接分析的手段.

基于矩阵分解的光交换机分组调度算法

研究基于矩阵分解的光交换机分组调度算法。首先讨论了一种将双随机矩阵快速分解为置换矩阵的算法,随后提出了依据其队长在线调度置换矩阵的p-LQF算法。仿真显示p-LQF的平均分组时延接近甚至低于LQF,在业务强度较大时远低于i-LQF。证明了p-LQF对于符合强大数定理的任何可接入业务是稳定的。然后讨论了p-LQF算法对分组动态到达的适应性。最后说明了p-LQF对矩阵进行有限量化以降低算法复杂度时依然能保持系统稳定。

基于FCP的交换结构研究

FCP是在存储区域网中用FC协议承载SCSI数据的一种通信方式,它不同于一般的面向无连接的IP通信,也与通常的专线连 接有区别。另外,在通信过程中存在控制信息和数据信息两种数据包,即长包和短包。它不是定长分组,但它又与传 统的变长分组有区别。由于FCP通信的特殊性,需要研究哪种交换结构最适合其要求。通过对VOQ+Crossbar、共享缓存 和一种双平面交换结构的仿真分析表明,双平面交换结构在性能上有一定的优势。

通用高速分组交换调度算法

在iSLIP算法的基础上,应用二部图匹配中对角线数据无竞争的数学原理,采用关联指针的处理方法,提出了一种基于虚拟输出排队(VOQ)缓冲模式下的高速交换调度算法——迭代的关联指针轮转(i-CPRR)算法。该算法简化了指针的轮转方式,降低了设计难度。仿真表明,该算法减少了调度过程中的迭代次数,提高了算法在高负载条件下的带宽利用率,从而降低了交换系统的数据延时和VOQ队列深度,在高速交换系统中具有广泛的应用价值。

星载交换机中高性能队列管理器的研究与实现

针对星载交换机中硬件处理速度和存储器容量受限的情况,设计实现了一个高性能队列管理器。采用虚拟输出排队机制改善输入缓存中存在的队头阻塞问题;使用前向地址指针pre_addr和后向地址指针nxt_addr控制信元的写入和读出。通过ModelSim SE行为级时序仿真可知,其能够达到星载交换机的队列时延要求,具有较高的交换性能及稳定性。

一种负载平衡的太比特路由器调度算法

研究了基于多级交换结构的太比特路由器分组调度算法．基于一种扩展的负载平衡两级Birkhoff-von Neuman交换结 构,提出了一种新的分组调度算法DRLB-BvN(dynamic resequencing load balanced Birkhoff-von Neuman)．DRLB-BvN分组调 度算法是根据最近的信元延迟情况动态调整年龄门限值的时间戳机制,该算法可以很好解决Chang等人提出的负载平衡 Birkhoff-von Neuman调度算法的信元失序问题,并且通过仿真结果表明:与DRLB-BvN算法相比,性能没有明显下降．

光纤通道交换机线卡中VOQ的设计与实现

介绍了1Gb/s速率8×8光纤通道交换机的体系结构,并详细论述了光纤通道交换机转发引擎中基于FPGA的VOQ的设计与实现。经过时序仿真与系统测试,验证了VOQ设计的正确性。