交换调度算法

一技＝术

交流　维普资讯 ¨ｌ　－。　一　０　ｊ　０　０　◇　＿塞．．　０　骥　塞堕馨　

同的出口边缘路由器地址、具有相同服务质量要求的ｌＰ分　

组组成。ＯＢＳ的特点是：突发数据分组（ＤＢ）和控制分　

组（ＢＨＰ）的传输在物理信道和时间上是分离的，控制分　

组提前于突发数据分组发送，而突发数据分组等待一定时　

间（偏置时间）后，不需等待回复确认信息，直接在预先　

确定的信道上发送。在核心节点上，控制分组经过光／电　

／光交换和电信息处理，为相应的光突发数据分组预留资　

源，使突发数据分组实现全光透明传输。　

２数据信道调度算法　

在ＯＢＳ网络中，核心节点根据到达的ＢＨＰ中包含的　

信息为后续到达的数据包ＤＢ安排合适的数据信道一信道　

调度。即当相应的ＢＨＰ到达核心路由器后，选择一条在　

ＤＢＡ０达光交换矩阵时可用的数据信道作为输出信道。当　

没有可用信道时，ＤＢ以及相应的ＢＨＰ将被丢弃。因此在　

ＯＢＳ网络核心节点处设计信道调度算法主要需要考虑以下　

两个方面：　（１）ＤＢ的丢失率；　（２）算法执行时间。一　

个理想的调度算法应该在ＤＢＡ０达前，能够尽快地处理相　

应的ＢＨＰ，并尽可能为该ＤＢ找到合适的信道。一个有效　

的调度算法可以通过快速地调度来降低ＤＢ的丢失率，并　

且提高网络带宽的利用率。　

２．１最近可用信道算法（ＬＡＵＣ）　

首先假设每个光核心路由器有　个ＦＤＬｓ，第ｉ个ＦＤＬ　

可以延时Ｑｉ（１　ｉ　Ｂ，Ｑ０＝０），其中Ｑ　＝ｉ×Ｄ　

（Ｄ为延时单元）。假设不考虑交换时间，不使用ＦＤＬ的　

情况下，ＤＢ到达光交换矩阵的时间和离开的时间相同。　

最近可用信道算法　只保留每个输出数据信道的最近　

使用时间（ＬＵＴ，Ｌａｓｔ　Ｕｓｅｄ　Ｔｉｍｅ），对于有Ｋ个数据信道，　

令ｆ，表示第，个信道的最近可用时间。ＬＡＵＣ算法的基本思　

想是为到达的数据突发选择最近可用未调度数据信道，　

假定ＤＢ到达核心节点的时刻为ｔ，ＤＢ的长度为Ｌ（用时　

第１　１卷第３期　２０１０年６月　信息工程大学学报　Ｊｏｕｒｎａｌ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ｕｎｉｖｅｒｓｉｔｙ　Ｖ０１．１１　ＮＯ．３　Ｊｕｎ．２０１０　

基于多下一跳路由的交换结构及调度算法　

侯晓颖，陈庶樵，朱　通　

（国家数字交换系统工程技术研究中心信息工程大学，河南郑州４５０００２）　

摘要：传统单下一跳路由已无法满足日益增长的网络应用的需求。基于多一下跳路由机制，提　出一种区分排队的多个可选端口输出交换结构以及双指针最大权重优先调度算法。该算法在　

区分排队的基础上对单、多输出端口分组使用双指针协同调度，实现交换端口的分布式调度和　动态匹配。仿真实验表明，该交换结构在多下一跳路由业务条件下具有良好的时延性能，该算　法保证了吞吐量和时延性能的同时，降低了实现复杂性，提高了交换结构的处理速度。　

关键词：多下一跳路由；交换结构；调度算法　中图分类号：ＴＮ９１５．０７　文献标识码：Ａ　文章编号：１６７１—０６７３（２０１０）０３—０２６１一Ｏ５　

Ｍｕｌｔｉ－Ｎｅｘｔ－Ｈｏｐ　Ｓｗｉｔｃｈｉｎｇ　Ｆａｂｒｉｃ　ａｎｄ　Ｓｃｈｅｄｕｌｉｎｇ　Ａｌｇｏｒｉｔｈｍ　

ＨＯＵ　Ｘｉａｏ—ｙｉｎｇ，ＣＨＥＮ　Ｓｈｕ—ｑｉａｏ，ＺＨＵ　Ｔｏｎｇ　

（Ｎａｔｉｏｎａｌ　Ｄｉｇｉｔａｌ　Ｓｗｉｔｃｈｉｎｇ　Ｓｙｓｔｅｍ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ｔｅｃｈｎｏｌｏｇｉｃａｌ　Ｒｅｓｅａｒｃｈ　Ｃｅｎｔｅｒ，Ｉｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ｕｎｉｖｅｒｓｔｉｔｙ，　Ｚｈｅｎｇｚｈｏｕ　４５０００２，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｔｒａｄｉｔｉｏｎａｌ　ｓｉｎｇｌｅ　ｎｅｘｔ—ｈｏｐ　ｒｏｕｔｉｎｇ　ｈａｓ　ｂｅｅｎ　ｕｎａｂｌｅ　ｔｏ　ｍｅｅｔ　ｔｈｅ　ｎｅｅｄｓ　ｏｆ　ｔｈｅ　ｉｎｃｒｅａｓｉｎｇ　ｎｅｔｗｏｒｋ　ａｐｐｌｉｃａｔｉｏｎｓ．Ｂａｓｅｄ　ｏｎ　ｍｕｌｔｉ—ｈｏｐ　ｒｏｕｔｉｎｇ　ｍｅｃｈａｎｉｓｍ，ｐｒｏｐｏｓｅｓ　ａ　ｍｕｌｔｉ—ｏｕｔｐｕｔ　Ｓｗｉｔｃｈｉｎｇ　ｆａｂ－　ｒｉｃ　ａｎｄ　ｄｕａｌ・ｐｏｉｎｔｅｒ　ｍａｘｉｍｕｍ－ｗｅｉｇｈｔ－ｆｉｒｓｔ　ｓｃｈｅｄｕｌｉｎｇ　ａｌｇｏｒｉｔｈｍ．Ｏｎ　ｔｈｅ　ｂａｓｉｓ　ｏｆ　ｄｉｓｔｉｎｇｕｉｓｈｉｎｇ　ｑｕｅｕ—　

第２５卷第７期　２００８年７月　计算机应用研究　Ａｐｐｌｉｃａｔｉｏｎ　Ｒｅｓｅａｒｃｈ　ｏｆ　Ｃｏｍｐｕｔｅｒｓ　Ｖ０１．２５　Ｎｏ．７　Ｊｕ１．２００８　

可扩展网络交换调度系统的分布式迭代算法　

胡庆生，徐植，仲建锋　

（东南大学射频与光电集成电路研究所，南京２１００９６）　

摘要：提出了一种最长队列优先的分布式迭代算法。与现有算法不同的是，该算法针对可扩展网络交换调度　

结构的特点，为处于最高优先级的调度器安排了两次迭代。其中的第一次迭代实现最长虚拟输出队列（ＶＯＱ）的　

查找，并且在最高优先级时隙之前的一个时隙完成，以缩短信号的处理时间。仿真结果表明，本算法与现有算法　相比，在大流量的ｕｎｉｆｏｒｍ流量模式下，延时性能与吞吐率获得了明显的提高；同时，该算法的硬件代价小，有效　

地实现了性能和复杂度的良好折中。　关键词：输入队列交换；可扩展；分布式迭代；虚拟输出队列　

中图分类号：ＴＰ３０１．６；ＴＰ３９３　文献标志码：Ａ　文章编号：１００１．３６９５（２００８）０７—２ｌ１５．０３　

Ｄｉｓｔｒｉｂｕｔｅ　ｉｔｅｒａｔｉｏｎ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｆａｉｒ　ｓｃａｌａｂｌｅ　ｓｃｈｅｄｕｌｉｎｇ　ａｒｃｈｉｔｅｃｔｕｒｅｓ　

ＨＵ　Ｑｉｎｇ—ｓｈｅｎｇ，ＸＵ　Ｚｈｉ，ＺＨＯＮＧ　Ｊｉａｎ—ｆｅｎｇ　（Ｉｎｓｔｉｔｕｔｅ　ｏｆＲＦ－＆ＯＥ－ｌＣｓ，Ｓｏｕｔｈｅａｓｔ　Ｕｎｉｖｅｒｓｉｔｙ，Ｎａ　ｎｇ　２１００９６，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ｔｈｉｓ　ｐａｐｅｒ　ｒｅｐｒｅｓｅｎｔｅｄ　ａ　ｎｅｗ　ｄｉｓｔｒｉｂｕｔｅｄ　ｉｔｅｒａｔｉｏｎ　ａｌｇｏｒｉｔｈｍ．Ｄｉｆｆｅｒｅｎｔ　ｆｒｏｍ　ｅｘｉｓｔｉｎｇ　ａｌｇｏｒｉｔｈｍｓ，ｔｈｅ　ｐｒｏｐｏｓｅｄ　ａｌｇｏ—　ｒｉｔｈｍ　ｄｉｓｔｒｉｂｕｔｅｄ　ｔｈｅ　ｍｕｌｔｉ—ｉｔｅｒａｔｉｏｎｓ　ｉｎ　ｓｅｑｕｅｎｔ　ｃｅｌｌ　ｔｉｍｅｓ．Ｉｎ　ｔｈｅ　ｆｉｒｓｔ　ｉｔｅｒａｔｉｏｎ　ｔｈｅ　ｌｏｎｇｅｓｔ　ｑｕｅｕｅ　ｗａｓ　ｐｉｃｋｅｄ　ｏｕｔ　ａｎｄ　ｓａｖｅｄ　ａｓ　ｔｈｅ　ｓｃｈｅｄｕｌｉｎｇ　ｒｅｓｕｌｔ　ｉｎ　ｔｈｅ　ｃｅｌｌ　ｔｉｍｅ　ｉｕｓｔ　ｂｅｆｏｒｅ　ｔｈｅ　ｈｉｇｈｅｓｔ　ｐｒｉｏｒｉｔｙ　ｃｅｌｌ　ｔｉｍｅ　ｉｎ　ｏｒｄｅｒ　ｔｏ　ｒｅｄｕｃｅ　ｔｈｅ　ｓｃｈｅｄｕｌｉｎｇ　ｔｉｍｅ．Ｔｈｅ　ｎｅｗ　ａｌｇｏｒｉｔｈｍ　ａｃｈｉｅｖｅｄ　ｂｅｔｔｅｒ　ｐｅｒｆｏｒｍａｎｃｅ　ｏｎ　ａｖｅｒａｇｅ　ｄｅｌａｙ　ａｎｄ　ｔｈｒｏｕｇｈｐｕｔ　ｕｎｄｅｒ　ｈｅａｖｙ　ｌｏａｄ　ｏｆ　ｕｎｉｆｏｒｉＢ　ｔｒａｆｆｉｃ　ｍｏｄｅｌ　ｃｏｍｐａｒｅｄ　ｔｏ　ｔｈｅ　ｅｘｉｓｔｉｎｇ　ａｌｇｏｒｉｔｈｍｓ．Ｍｅａｎｗｈｉｌｅ，ｔｈｉｓ　ｐｒｏｐｏｓｅｄ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｆａｉｒｌｙ　ｅａｓｙ　ｆｏｒ　ｈａｒｄｗａｒｅ　ｉｍｐｌｅｍｅｎｔａｔｉｏｎ．　Ｋｅｙ　ｗｏｒｄｓ：ｉｎｐｕｔ—ｑｕｅｕｅｄ　ｓｗｉｔｃｈ；ｓｃａｌａｂｌｅ；ｄｉｓｔｒｉｂｕｔｅｄ　ｉｔｅｒａｔｉｏｎ；ＶＯＱ　

工程实践皿应用技术　

基于ＶＯＱ输入缓存交换系统调度算法研究　

赵增辉，李文江　

（中国电子科技集团公司第５４研究所，河北石家庄０５００８１）　

摘　要：基于ＶＯＱ缓存策略的信元调度算法是提升交换系统性能的关键因素。介绍了３种富有代表性的调度算　

法：ｉＳＬＩＰ算法、ｉＬＱＦ算法和ＤＰＡ算法。ｉＳＬＩＰ算法易于硬件实现，不大于ＩＧ．ｇ２Ｎ次迭代即可实现收敛，但时于突发通　

信效率不高，适用于中小规模的高速交换结构；ｉＬＱＦ算法调度效率高，但硬件实现较为困难，且时延较大，目前应用　

较少：；ＤＰＡ算法可以用简单的组合逻辑实现，时延小，但效率不高，适用于重载大规模的高速交换结构。　关键词：交换结构；ＶＯＱ；ｉＳＬＩＰ；ｉＬＱＦ；ＤＰＡ　

中图分类号：ＴＮ９１５．０５　文献标识码：Ａ　文章编号：１００３—３１１４（２００６）０６—５９—３　

Ｓｔｕｄｙ　ｏｎ　ｓｃｈｅｄｕｌｉｎｇ　ａｌｇｏｒｉｔｈｍｓ　ｆｏｒ　ＶＯＱ　ｉｎｐｕｔ－ｂｕｆｆｅｒ　ｓｗｉｔｃｈｅｓ　

ＺＨＡＯ　Ｚｅｎｇ—ｈｕｉ，ＬＩ　Ｗｅｎ—ｊｉａｎｇ　

（Ｔｈｅ　５４ｔｈ　Ｒｅｓｅａｒｃｈ　Ｉｎｓｔｉｔｕｔｅ　ｏｆ　ＣＥＴＣ，Ｓｈｉｊｉａｚｈｕａｎｇ　Ｈｅｂｅｉ　０５００８　１，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｃｅｌｌ　ｓｃｈｅｄｕｌｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　ＶＯＱ　ｉｎｐｕｔ－ｂｕｆｆｅｒ　ｓｔｒａｔｅｇｙ　ｉｓ　ａ　ｋｅｙ　ｆａｃｔｏｒ　ｏｆ　ｉｍｐｒｏｖｉｎｇ　ｓｗｉｔｃｈ　ｐｅｒｆｏｒｍａｎｃｅ．Ｔｈｅ　ｔｈｒｅｅ　

ｋｉｎｄｓ　ｏｆ　ｒｅｐｒｅｓｅｎｔａｔｉｖｅ　ｓｃｈｅｄｕｌｉｎｇ　ａｌｇｏｒｉｔｈｍｓ（ｉＳＬＩＰ，ｉＬＱＦ　ａｎｄ　ＤＰＡ　ａｌｇｏｒｉｔｈｍ）ａｒｅ　ｄｅｓｃｒｉｂｅｄ　ｉｎ　ｔｈｉｓ　ｐａｐｅｒ．ｉＳＬＩＰ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｅａｓｉｌｙ　ｉｍｐｌｅｍｅｎｔｅｄ　ｉｎ　ｈａｒｄｗａｒｅ　ａｎｄ　ａｃｃｏｍｐｌｉｓｈｅｓ　ｃｏｎｖｅｒｇｅｎｃｅ　ｂｙ　ｎｏ　ｍｏｒｅ　ｔｈａｎ　ｌｏｇｚＮ　ｔｉｍｅｓ，ｂｕｔ　ｉｔ　ｈａｓ　ｎｏｔ　ｈｉｇｈ　ｅｆｆｉｃｉｅｎｃｙ　ｉｎ　ｂｕｒｓｔ