高性能路由器分组调度算法研究
作者:
基金项目:

国家自然科学基金资助项目(69682002;69725003);国家863高科技发展计划资助项目(863-306-2D-07-01)


Study on a Packet Scheduling Algorithm in High Performance Routers
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [18]
  • |
  • 相似文献 [20]
  • | | |
  • 文章评论
    摘要:

    Internet同时面临着两个问题:更快的交换路由结构和引入服务质量(QoS)保证.每个问题都可以独立解决.高性能路由器可以用输入缓冲的交叉开关(crossbar)代替共享内存来获得更快的速度;QoS能够通过分组公平排队算法PFQ(packet fair queuing)来得到.然而到目前为止,这两个问题的解决还是互斥的--所有的分组公平排队算法研究都需要路由器采用输出排队或者集中式共享内存.基于输入输出结合排队CIOQ(combined input output queuing)结构,设计和实现了一种分

    Abstract:

    Internet is facing two problems simultaneously: a faster switching/routing infrastructure and guaranteed quality-of-service (QoS). Each problem can be solved independently. High performance routers can be made faster by using input-queued crossbars instead of shared memory systems. QoS can be provided by usingpacket fair queuing (PFQ) algorithm. Until now, however, the two solutions have been mutually exclusive-all ofthe work on PFQ algorithm has required that routers use output-queuing or centralize shared menory.In this paper, on the basis of CIOQ(combined input output queuing)architecture,a packt scheduling algorithm DF2Q(distributed feedback fair queeuing)is designed and implemented.The most important feature of this algorithm is the introducing of feedback mechanism.the perfomance of DF2Qis analyzed and discussed.Experimental resuts show that it can avoid internal congestion effectively and improve the efficiency of resource utilizing.

    参考文献
    [1] McKeown,N.,Izzard,M.,Mekkittikul,A.,et al.The tiny tera: a packet switch core.IEEE Micro,1997,17(1):26~33.
    [2] Digital Equipment Corporation.GIGAswitch.1997,http://www.networks.digital.com.
    [3] Ascend Communications.GRF family of switches.1998,http://www.ascend.com.
    [4] Chuang,S.,Goel,A.,McKeown,N.,et al.Matching output queueing with a combined input/output-queued switch.IEEE Selected Areas in Communications,1999,17(6):1030~1039.
    [5] Goyal,P.,Vin,H.M.,Chen,H.Start-Time fair queuing: a scheduling algorithm for integrated services.IEEE/ACM Transactions on Networking,1997,5(5):690~704.
    [6] Bennett,J.C.R.,Zhang,H.WF2Q: worst-case fair weighted fair queuing.In: Tatsuya,Suda,ed.,Proceedings of the Infocom'96.Jersey: IEEE Piscataway Press,1996.120~128.
    [7] Demers,A.,Keshav,S.,Shenker,S.Analysis and simulation of a fair queue algorithm.Internetworking: Research and Experience,1990,1(1):3~26.
    [8] Zhang,L.Rate-Based scheduling discipline for packet switching networks.Electronics Letters,1995,31(14):1130~1131.
    [9] Karol,M.J.,Hluchyj,M.G.,Morgan,S.P.Input versus output queuing on a space division packet switch.IEEE Transactions on Communications,1987,35(7):1347~1356.
    [10] McKeown,N.,Anantharam,V.,Walrand,J.Achieving 100% throughput in an input-queued switch.IEEE Transactions on Communications,1999,47(8):1260~1267.
    [11] Anderson,T.,Owicki,S.,Saxe,J.,et al.High speed switch scheduling for local area networks.ACM Transactions on Computer Systems,1992,11(4):319~352.
    [12] Simcoe,R.,Pei,T.Perspectives on ATM switch architecture and the influence of traffic patterns on switch design.Computer Communication Review,1995,25(2):93~105.
    [13] Chiussi,F.M.,Xia,Y.,Kumar,V.P.Performance of shared-memory switches under multicast bursty traffic.IEEE Selected Areas in Communications,1997,15(3):473~487.
    [14] Zhang,H.Service disciplines for guaranteed performance service in packet-switching networks.Proceedings of the IEEE,1995,83(10):1374~1399.
    [15] Parekh,A.K,.Gallager,P.G.A generalized processor sharing approach to flow control in integrated services networks: the multiple node case.IEEE Transactions on Networking,1994,2(2):137~150.
    [16] Golestani,S.A self-clocked fair queueing scheme for broadband applications.In: Wieselthier,J.E.,ed.Proceedings of the IEEE INFOCOM'94.New Jersey: IEEE Piscataway Press,1994.636~646.
    [17]Stoica,I.,Abdel-Wahab,H.An efficient packet service algorithm for high speed ATM switches.Journal of Computer Communications,1998,21(9):839~852.
    [18]Tabatabaee,V.,Georgiadis,L.,Tassiulas,L.QoS provisioning and tracking fluid policies in input queuing switches.In: Moshe,Sidi,ed.Proceedings of the INFOCOM'2000.New Jersey: IEEE Piscataway Press,2000.1624~1633.
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

江勇,吴建平,徐明伟.高性能路由器分组调度算法研究.软件学报,2002,13(4):621-628

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

京公网安备 11040202500063号