摘 要

本文研究了跨数据中心网络的紧急备份问题，这种备份是在可预测性灾难发生时紧急触发的，考虑的问题是如何在预警时间内尽可能地优化备份过程，使得备份效益最大化。首先，区分不同数据的价值，在此基础上以备份效益为目标，建立动态网络优化模型；接着，为了降低时变模型的复杂度，采用时间扩展网络的方法将动态模型转化为与时间无关的静态流模型；时间扩展网络的方法虽然使问题大大简化，但同时网络拓扑规模变得巨大，求解有很大困难，为此，采用一种高效的分布式算法——交替方向乘子算法，并行地对模型进行求解；最后，进行了相关的数值仿真实验，结果显示，交替方向乘子算法能实现最大化的备份效益，且算法运行时间优于所设计的其他几个算法。

关键词：跨数据中心网络、紧急备份、时间扩展网络、交替方向乘子

Abstract

This thesis addresses the emergency backup problem in inter-datacenter network , which is triggered in response to predictable destructive events. We consider scheduling and routing the emergency backup to maximize the utility within an early warning time. Specifically, we first formulate the utility-maximization network model with consideration of the value of data. Then we leverage the time-expanded network approach to translate the dynastic model into a static one, which greatly simplifies the problem at the cost of a considerable increase in the size of the network. To finally solve this problem, a time-efficient and distributed algorithm called alternating direction method of multipliers is proposed, computing in parallel. We perform numerical simulations to evaluate the algorithm and results show that our algorithm outperforms some existing algorithm on both utility and time performance.

Key Words: inter-datacenter network, emergency backup, time-expanded network，alternating direction method of multipliers

目 录

摘 要 I

Abstract II

第 1 章 绪论 1

1.1 课题背景 1

1.2 国内外研究现状 1

1.3 课题的目的和意义 2

1.4 论文章节安排 3

第 2 章 备份效益最大化模型的建立 4

2.1 建模准备 4

2.1.1 数据中心网络 4

2.1.2 网络模型 4

2.1.3 数据备份的效益函数 5

2.2 动态网络模型的建立 6

2.2.1 模型的数学描述 6

2.2.2 模型复杂度分析 7

2.3 基于时间扩展网络的模型重建 8

2.3.1 时间扩展网络算法简介 8

2.3.2 动态网络模型重建 9

2.3.3 模型复杂度分析 11

第 3 章 交替方向乘子算法 12

3.1 拉格朗日函数及KKT条件 12

3.2 对偶理论 13

3.2.1 对偶问题 14

3.2.2 对偶上升法 14

3.2.3 对偶分解法 15

3.3 增广的拉格朗日函数和乘子法 16

3.4 ADMM算法 16

3.4.1 ADMM算法的综述 16

3.4.1 ADMM算法的构建 17

3.4.3 ADMM算法的收敛性 17

3.5 本章小结 18

第 4 章 基于ADMM算法的模型求解 19

4.1 ADMM应用 19

4.1.1变量z的优化 20

4.1.2变量b的优化 21

4.2 对比算法 22

4.2.1 CVX 22

4.2.2 最大流算法 23

4.2.3 高效益流优先算法 23

4.2.4 基于时间扩展网络的最大流算法 23

4.2.5 基于时间扩展网络的高效益流优先算法 23

4.3 模型求解 24

4.4 结果分析 24

4.4.1 对偶间隙 24

4.4.2 灵敏性分析 25

4.4.3 鲁棒性分析 25

4.4.4 对比算法 26

第 5 章 总结 29

5.1 课题主要工作及完成情况 29

5.2 模型的评价和推广 29

5.3 算法的评价和分析 30

参考文献 31

致 谢 33

第 1 章 绪论

1.1 课题背景

随着密集型数据应用的快速发展，我们已经进入了大数据时代，各大企业都将数据视为宝贵的财富，例如谷歌、亚马逊、微软等公司，分别在全球不同地方建立多个数据中心（DC），这些数据中心拥有巨量的数据，为众多应用提供服务。众所周知，数据中心会因为自然灾害等因素而受到损毁，使得数据中心的拥有者承受巨大的损失，例如，2008年四川地震损毁了超过60家企业的数据中心^[1]，2011年Tohoku地震损毁了数十个数据中心，一些公司甚至因为丢失关键文件而宣布破产^[2]。为此，数据中心的灾备工作是十分有必要的，各个数据中心可以通过合作进行数据备份，建立信息冗余机制，以便应对自然灾害或者人为攻击等造成的服务中断。很多企业都有自己的数据备份系统，这些备份一般包括两种形式：常规备份和紧急备份。

常规备份是在一个周期性的时间（如每月、每周甚至每天）将数据备份到其他设备上，从而实现数据安全的备份机制。众所周知，数据中心容易受到自然灾害（如地震、海啸、台风等）的影响而损毁，其他一些因素也会影响到数据中心的安全，如突然断电、设备故障、人为误操作等。一旦数据中心发生故障，上面存储的数据会丢失，支持的服务会瘫痪，给企业带来严重的经济损失，为此，绝大多数企业都有自己的常规备份机制，以保证企业的效益。数据备份过程中会占用巨大的带宽资源，往往导致网络堵塞，影响到正常的网络服务，所以大多数企业的数据备份通常在深夜进行，并在尽可能短的时间内完成。如何设计优化备份机制，使得备份时间更短，是众多企业和研究者所关心的问题。

紧急备份是在可预测性灾难（如台风、海啸、地震、导弹袭击）等紧急事件发生时触发的备份机制，这类事件在损毁数据中心前通常有一个短暂的预警时间，为了降低数据中心拥有者的损失，必须要在这个时间内进行数据的紧急备份。与常规备份不同，紧急备份不一定能实现所有数据的成功备份，为此要对数据加以区分，设计和优化备份方案，以使备份效益最大。

1.2 国内外研究现状

国内外已经有很多人研究过常规备份，他们以降低资源费用或缩短备份时间为目标，为数据备份提出了方案。文献[3]提出了一种高效数据备份和恢复算法EDBRA，尽可能消除数据中的重复部分以提高备份效率；文献[4],[5]利用多DC云备份系统，提出了分层原子广播（hierarchical atomic broadcast）、失效转移（failover）等的备份机制；Wood在文献[6]中讨论了将灾备作为一种云服务并且分析了基于此方法的经济效益；文献[7]中也提出了一种应对灾难的资源分配机制；文献[8]研究了多DC间大模块数据传输问题的路由和带宽分配；文献[9]引入了备份窗口的概念，即多DC间备份新数据的时长，备份窗口在评估备份方案时是个重要的参数，因为延时过长的备份窗口不仅会影响DC备份的正常运行，可能也会造成数据拥塞。