文 献 综 述
研究背景
随着现代社会的高速发展，云计算、大数据等信息技术在不断普及和应用，数据中心始终处于核心地位。为不断满足用户的需求，数据中心网络面临着许多新的问题和挑战。如今越来越多的业务需要在虚拟机或服务器之间进行大量通信，数据传输的规模在增长[1]，通信也更为频繁，这导致数据中心内部流量急剧增长，并呈现出不同于互联网流量的新特性[2][3]。
为了应对日益增长的流量负载压力，数据中心网络通过负载均衡的实现，尽可能增加吞吐量、加强网络数据处理能力、提高网络的灵活性和可用性[4]。除了将流量负载均分到数据中心网络的路径上，负载均衡还要保障象流的高带宽需求、鼠流的低时延需求[5]。
在数据中心网络中，存在广泛的多路径路由算法，按照流量负载均衡的粒度可将负载均衡方案分为流级别、流片段级别和报文级别[6]。如基于软件定义网络（Softwareensp;Definedensp;Network，SDN）的数据总线网络动态流量调度方法，该算法利用SDN集中控制，具有全局视图的优点，可调度网络中的大象流。基于蚁群算法的动态多路径负载均衡（ant colony algorithm based dynamic multipath load balancing，ADMLB）算法可通过控制器获取网络负载信息，同时检测大象流并标记，然后调用改进的蚁群算法，根据大象流所需带宽选择多路径[7]。等价多路径（Equal-Cost Multipath Routing， ECMP）路由算法是目前IP网络中支持负载均衡的重要手段[8]，它是流级别的负载均衡方案[9]，开放式最短路径优先（Open Shortest Path First ， OSPF ） [10]、 中 间 系 统 到 中 间系 统（Intermediate System to Intermediate System，ISIS）[11][12]等各种路由协议也已明确允许 ECMP。结合RIP 协议（Routing Information Protocol）[13]，ECMP在现有商品交换机中已经得到了实现。因此研究ECMP的算法、模型与实现具有现实意义。
等价多路径路由协议
简介
等价多路径是一个能够在多种路径中选择相等代价数据包的路由选择技术。通过对数据包报头中的字段进行简单的哈希运算来选择每一个下一跳地址，将一条流静态映射到其中一条等价路径上[14]。ECMP 可充分利用数据中心网络拓扑的等价路径来实现流量的路径划分，提供网络的负载均衡。
借助于拓扑结构，为实现负载均衡，等价多路径路由（Equal-Cost Multipath，ECMP） [15]算法可提供并行相等跳数的路径。Fat-Tree拓扑结构已经被普遍运用在数据中心网络中，其网络结构是以交换机为中心的三层级联的多根树拓扑架构，可实现大规模数据中心网络的设备互联。它与传统的树形网络一样分为核心层、聚合层和边缘层，所有的服务器与边缘层的交换机互联。Fat-Tree结构的最大特点是可以支撑无阻塞网络，使用Fat-Tree结构可以更加方便直观地展示ECMP路由算法。
实现等价多路径的路由选择算法
主要实现在等价多路径路由的负载均衡算法有哈希阈值（Hash-Threshold）[16]、轮询算法、随机选择算法、模N算法和最高随机权重算法。其中，对于哈希阈值算法，路由器会对数据包中识别流的头字段进行哈希运算，得到一个键值（对于流的定义，一般认为五元组信息（源/目的 IP 地址、源/目的端口号、协议类型）相同的数据包为一条流）；再将键值的可能取值空间划分成N个区域，给不同的下一跳地址分配一个域；路由器使用键值在哪个区域来决定下一跳地址的路由。为选定下一跳地址，我们需要确定键值被包含在哪个区域，而各个区域的大小是相同的，我们可以得出：
因此哈希阈值算法在最优情况下复杂度为O(1)。对于轮询算法（round-robin），在接收数据包时，总是选择最近使用过的下一跳地址。对于一个给定的流来说，只要各个区域的边界是不变的，就会始终选择相应的下一跳地址。
干扰（disruption）是用来衡量有多少流量因为路由器的某些变化，使路由发生变化。当多条路径可供选择时，通过添加或删除路径比仅选择最佳路径更高效，因为多路径的变动可能导致数据包重新整理或丢失，因此需要最小化添加或删除下一段路径带来的影响。干扰比例可被定义为由于路由器原因发生路由变化的流量占总流量的比例。在删除一个区域K后，剩余的N-1个区域会均匀扩大来填满这个1/N的空间，因此每个区域的变化大小为1/N/(N-1)即1/(N(N-1))。除了两端的区域会开始的平移，直到编号为K的区域。可得到：
为得到最小值，将上式取导数，可得
以上是毕业论文文献综述，课题毕业论文、任务书、外文翻译、程序设计、图纸设计等资料可联系客服协助查找。
