等价多路径间流量分配调度算法研究

《等价多路径间流量分配调度算法研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、http://www.paper.edu.cn等价多路径间流量分配调度算法研究1233林伟，刘斌，唐毅（1．清华大学深圳研究生院广东深圳518055；2.香港城市大学香港；3．清华大学计算机科学与技术系，北京100084）lin-w04@mails.tsinghua.edu.cn摘要：为了减少网络拥塞并充分利用链路带宽，当在转发节点与目的子网间存在有多条等价路径（ECMPs）时，流量负载应该在ECMPs间均衡分配，并且属于同一个TCP流的IP分组应该按照相同顺序到达目的主机。1本文提出了一种基于LRUCache和计数统计的算法。该算法通过为每条ECMP分配

2、一个计数器，利用计数统计从而考虑到了IP分组的长度差异。使用相对计数以及对某些情况增加约束条件解决了计数器溢出问题。UDP分组只需要作为调节负载均衡的流量。更进一步，对于去往同一目的子网的不同主机的TCP流的时延差异被转化为cache中的表项失效的时间长度差。仿真实验表明，当ECMPs间的时延差不显著的情况下，只需要很小的存储空间，且每次cache查找只需要一个时钟周期，负载均衡接近最优，此时只有2%的分组出现乱序。关键词：流量分配；等价多路径；LRU；Cache；计数统计中图分类号：TP393.051引言随着Internet网络规模的的迅速扩大，其拓扑结

3、构日趋复杂。从流量工程、可靠性和网络安全等因素考虑，网络中的两个节点间部署了多条路径。目前，绝大部分单一路径路由协议都是基于dijkstra的最短路径算法，只有开销最小的路径被选为路由路径。按照这种算法，网络所提供的带宽没有被充分利用，有可能出现多条路径中的一条路径负载过重，而其他路径却处于空闲状态，如此将造成网络的局部拥塞。当IP分组经过多个节点之后，负载不均衡的情况可能会进一步加剧。如果存在多于一条的路径的开销近似相等，单一路径路由协议的计算结果会在这几条路径间变化，造成频繁的路由表更新，网络变得不稳定，性能也受到影响[1]。与单一路径路由协议不同，等

4、价多路径路由协议被提出用以解决上述的问题[2,3]。对于那些去往同一目的子网的IP分组，ECMPs被提供作为下一跳路由选择的候选路径，此处等价是指：从转发节点到目的子网间的这些路径的最短路径开销（例如延时或者经过的跳数）计算结果，在一定的精度下近似相等。当路由协议提供ECMPs时，为了充分利用可用带宽并降低路由的不稳定性，流量应该在ECMPs间均衡分配。在本文中，为了便于讨论，假设每条路径的带宽都相等；不相等的情况下，给每条路径附加一个权重参数来表示带宽的差异，流量应该根据权重参数在ECMPs间进行分配。2对于TCP分组，当属于同一个TCP连接流的分组从不

5、同路径转发时，就可能会出现乱序的问题。这是因为每条路径的时延并非精确相等，其时延可能会随着流量负载压力的变化而变化，因而有可能出现后转发的分组经过另一更短时延路径先于先转发的分组到达目的主机的情况。如果连续到达的乱序分组数小于TCP滑动窗口长度，TCP滑动窗口可以处理乱序的问题，不会造成网络性能的下降；否则，目的主机会发出重传请求，网络以及相关应用程序的性能会受到明显影响。因此，负载均衡问题以及分组保序问题应该被一同优化。如果分组按照轮转的方式转发,而不考虑分组长度的差异，负载均衡将达到最优，但是分组的乱序很严重。另一个极端，如果属于同一个流的分组都必须从

6、同一个路径转发，虽然分组可以被严格保序，但是负载均衡不能达到最优，其性能取决于流量分布。基金项目：国家自然科学基金（No.60373007；No.60573121）；中国-爱尔兰科学技术合作研究基金（CI-2003-02）；高等学校博士点基金（No.20040003048）；清华大学985基金（No.JCpy2005054）1LeastRecentlyUsedalgorithm2同一个流的分组是指其源IP地址（SIP）、目的IP地址（DIP），源端口号（SP），目的端口号（DP）和协议类型都相等。-1-http://www.paper.edu.cn当分组经

7、过若干跳之后，负载分配差异会愈加明显，这在Internet上是很常见的情况。本文首先提出了基于LRUCache和计数统计的算法（LCC），指出不需要严格约束属于同一个流的分组都从同一条路径转发。其次研究了由于流重定向造成的乱序的概率以及同一个流相邻两个分组的时间间隔之间的关系。在负载平衡时考虑到了分组长度的差别。由于UDP分组不需要保序，因此只需要将其在ECMPs间分配以满足负载均衡。本文结构如下，第2部分介绍了在ECMPs间流量分配的相关工作；第3部分阐述LCC算法的基本思想和实现结构；第4部分给出了LCC算法和其他算法的仿真实验结果，并在负载均衡以及分

8、组保序两方面进行了性能比较，对分组乱序进行了初步的理论分析；最后，