Multi-Step Scheduling Strategy in Input-Queued Switches
Affiliation:

  • Article
  • | |
  • Metrics
  • |
  • Reference [11]
  • |
  • Related
  • |
  • Cited by
  • | |
  • Comments
    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.

    Reference
    [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.
    Related
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

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

Copy
Share
Article Metrics
  • Abstract:3999
  • PDF: 4802
  • HTML: 0
  • Cited by: 0
History
  • Received:December 09,1999
  • Revised:April 17,2000
You are the first2034809Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063