输入缓冲交换开关的多步调度策略
作者:
基金项目:

国家自然科学基金资助项目(69933030)


Multi-Step Scheduling Strategy in Input-Queued Switches
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [11]
  • |
  • 相似文献 [20]
  • |
  • 引证文献
  • | |
  • 文章评论
    摘要:

    输入缓冲交换开关已经在越来越多的ATM交换机和高性能路由器中使用.对于独立的信元到达,VOQ(virtual output queueing)技术与LQF(1ongest queue first)和OCF(oldest cell first)等加权调度算法的结合使用可以使利用交换开关的吞吐率达到100%.然而LQF和OCF等加权调度算法过于复杂,无法用硬件实现.提出了多步调度策略,使得用硬件实现加权调度算法成为可能.在该策略下,对于独立的信元到达,LQF算法仍可以达到100%的利用开关吞吐率,并具有良好的

    Abstract:

    Input Queued switches are increasingly used in ATM switches and high performance routers. It has been proved that combining VOQ (virtual output queueing) technology and some weighted scheduling algorithms, such as LQF (longest queue first) and OCF (oldest cell first), the switch throughput can reach 100% for all cell arrivals with independent distributions. But the algorithms of LQF and OCF are so complicated that they cannot be easily implemented in hardware. A multi step scheduling strategy proposed in this paper makes it possible to implement the weighted in hardware. A multi-step scheduling strategy proposed in this paper makes it possible to implement the weighted scheduling algorithma in hardware. It is also proved that the switches based on the LQF by introducing the multi-step scheduling strategy can still get 100% throughput and the better delay property for arrivals with independent distributions.

    参考文献
    [1] Keshav, S. , Sharma, R. Issues and trends in router design. IEEE Communication Magazine, 1998,36(3):144~151.
    [2] Partridge, C. , Carvey, P. , Burgess, E. , et al. A 50-Gbps IP router. IEEE/ACM Transactions on Networking, 1998,6(3) :237~247.
    [3] McKeown, N. , Izzard, M. The tiny tera: a packet switch core. IEEE Micro, 1997,17(1):26~33.
    [4] McKeown, N. , Anantharam, V. , Walrand, J. Achieving 100% throughput in an input-queued switch. In: Proceedings of the IEEE Infocom'96. San Francisco, 1996. http:∥tiny-tera. stanford. edu/~nickm/papers. html.
    [5] Nick, McKeown, et al. A starvation-free algorithm for achieving 100% throughput in an input-queued switch. In: Proceedings of the ICCCN'96. 1996. http:∥tiny-tera. stanford. edu/~nickm/papers. html.
    [6] Mekkittikul, A. , McKeown N. A practical scheduling algorithm to achieve 100% throughput in input-queued switches.In: Proceedings of the IEEE Infocom'98. San Francisco, 1998. http:∥tiny_tera. stanford. edu/~nickm/papers. html.
    [7] McKeown, N. iSLIP: a scheduling algorithm for input-queued switches. IEEE Transactions on Networking, 1999,7(3):188~201. http:∥tiny-tera. stanford. edu/~nickm/papers. html.
    [8] Xie, Zheng, Li, Jian-ping. Network Algorithms and Complexity Theories. Changsha: Press of National University of Defence Technology, 1995 (in Chinese).
    [9] Paxson, V. , et al. Wide-Area traffic: the failure of poisson modeling. IEEE/ACM Transactions on Networking, 1995,3 (3) :226~244.
    [10] Meyn, K. Stability of queueing networks and schduling policies. IEEE Transactions on Automatic Control, 1995,40(2): 251~260.
    [11] 谢政,李建平.网络算法与复杂性理论.长沙:国防科学技术大学出版社,1995.
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

孙志刚,卢锡城.输入缓冲交换开关的多步调度策略.软件学报,2001,12(8):1170-1176

复制
分享
文章指标
  • 点击次数:3997
  • 下载次数: 4792
  • HTML阅读次数: 0
  • 引用次数: 0
历史
  • 收稿日期:1999-12-09
  • 最后修改日期:2000-04-17
文章二维码
您是第19794007位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号