期刊文献+

等价多路径间基于LRU Cache和计数统计的流量分配调度算法 被引量:2

Achieving Optimized Traffic Sharing over Equal-Cost-Multi-Paths Using LRU-based Caching with Counting Scheme
下载PDF
导出
摘要 为了减少网络拥塞并充分利用链路带宽,当在转发节点与目的子网间存在有多条等价路径(ECMPs)时,流量负载应该在ECMPs间均衡分配,并且属于同一个TCP流的IP分组应该按照相同顺序到达目的主机.本文提出了一种基于LRU(Least Recently Used Algorithm)Cache和计数统计的算法.该算法通过为每条ECMP分配一个计数器,利用计数统计从而考虑到了IP分组的长度差异.使用相对计数以及对某些情况增加约束条件解决了计数器溢出问题.UDP分组只需要作为调节负载均衡的流量.更进一步,对于去往同一目的子网的不同主机的TCP流的时延差异被转化为cache中的表项失效的时间长度差.仿真实验表明,当ECMPs间的时延差不显著的情况下,只需要很小的存储空间,且每次cache查找只需要一个时钟周期,负载均衡接近最优,此时只有2%的分组出现乱序. In order to reduce network congestion and fully use link bandwidth, when there are Equal-cost-multi-paths (ECMPs) between a forwarding node and a destination subnet, traffic load should be balanced among ECMPs and packets of the same TCP flow should reach destination host in the same order. An algorithm called LRU-based caching with counting (LCC) is proposed. Packet length differentiation is considered to achieve load balance by adapting a counter for each ECMP, and counter overflow is solved by relative counting and restrictions. UDP packets only need to be concemed to achieve load balance. Furthermore,flow delay differentiation forwarding to different hosts of the same destination subnet is transformed to entries in cache invalided time period difference. Simulation shows that when delay differentiation among ECMPs is not significant, storage requirement is small,only one cycle is needed for each cache lookup,load balance is near optimal,and only 2% of packets are out of order.
出处 《电子学报》 EI CAS CSCD 北大核心 2008年第1期32-38,共7页 Acta Electronica Sinica
基金 国家自然科学基金(No.60373007,60573121) 中国-爱尔兰科学技术合作研究基金(No.CI-2003-02) 高等学校博士点基金(No.20040003048) 清华大学985基金(No.JCpy2005054)
关键词 流量分配 等价多路径 LRU CACHE 计数统计 traffic splitting ECMPs LRU cache counting
  • 相关文献

参考文献2

二级参考文献19

  • 1[1]Fuller V, Li T, Yu J, Varadhan K. Classless inter-domain routing (CIDR): An address assignment and aggregation strategy. RFC1519, 1993.
  • 2[2]Hinden R, Deering S. IP version 6 addressing architecture. RFC 2373, 1998.
  • 3[3]DegerMark M, Brodnik A, Carlsson S, Pink S. Small forwarding tables for fast routing lookups. In: Handley M, et al. ed. Proc. of the ACM SIGCOMM. New York: ACM Press, 1997. 3~14.
  • 4[4]Gupta P, Lin S, Mckeown N. Routing lookups in hardware at memory access speeds. In: Charny A, ed. Proc. of the IEEE INFOCOM. San Franciso: IEEE Communications Society, 1998.
  • 5[5]Waldvogel M, Varghese G, Turner J, Plattner B. Scalable high speed IP routing lookups. In: Handley M, et al. ed. Proc. of the ACM SIGCOMM. New York: ACM Press, 1997. 25~36.
  • 6[6]Lampson B, Srinivasan V, Varghese G. IP lookups using multiway and multicolumn search. IEEE/ACM Trans. on Networking, 1999,7(3):324~334.
  • 7[7]Nilsson S, Karlsson G. IP address lookup using LC-Tries. IEEE Journal on Selected Areas in Communications, 1999, 17(6):1083~1092.
  • 8[8]Liu H. Routing table compaction in ternary CAM. IEEE Micro, 2002,22(1):58~64.
  • 9[9]Shah D, Gupta P. Fast updating algorithms for TCAMs. IEEE Micro, 2001,21(1):36~47.
  • 10[10]Michigan University. Merit network. Internet performance and analysis project. http://www.merit.edu/~ipma

共引文献61

同被引文献20

  • 1明叔亮,陈玉鹏,徐龙建,张瑜,户才和.P2P:革命已经开始[J].互联网周刊,2006(7):24-26. 被引量:4
  • 2张震波,杨鹤标,马振华.基于LRU算法的Web系统缓存机制[J].计算机工程,2006,32(19):68-70. 被引量:30
  • 3唐治果,李乐民,虞红芳.针对MPLS网络流量工程的链路关键性路由算法[J].电子与信息学报,2007,29(5):1187-1190. 被引量:13
  • 4Masip-Bruin X,Yannuzzi M,Domingo-Pascual J,et al.Research challenges in QoS routing[J].IEEE Computer Communications,2006,29(5):563-581.
  • 5Orda A.QoS routing:Challenges and solution approaches[C]∥IEEE Computer Society.2005:2-xxii.
  • 6Sridharan A,Guérin R,Diot C.Achieving near-optimal traffic engineering solutions for current OSPF/IS-IS networks[J].IEEE/ACM Trans.Netw,2005,13(2):234-247.
  • 7Wang Z,Wang Y,Zhang L.Internet traffic engineering without full-mesh overlaying[C]∥Proc.INFOCOM 2001.2001:565-571.
  • 8Fortz B,Thorup M.Internet Traffic Engineering by Optimizing OSPF Weights[C]∥Proceedings of the INFOCOM 2000.2000:519-528.
  • 9Cao Z,Wang Z,Zegura E.Performance of hashing-based schemes for Intemet load balancing[C]∥Proceedings of IEEE INFOCOM.2000,1:332-341.
  • 10Zinin A,Cisco Routing.PacketForwarding and Intra-domain Routing Protocals[M].Section 5.5.1:Addison Wesley,2002.

引证文献2

二级引证文献4

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部