氏学位名Ma, Lisheng

名博士（システム情報科学）

学 位 記 番 号

第３６号

学位授与年月日

平成２９年９月２１日

学位論文題目

Data Center Network Placement and Data Backup Against Region Failures

論文審査委員

主査 姜 暁鴻副査 稲村 浩副査 藤野 雄一
副査 和田 雅昭論

文 要 旨

Rapid growth of cloud computing has enabled a wide scope of new applications such as
e-commerce and social networking. As the underlying supporting infrastructure, data center
networks (DCNs) deployed in geographically distributed (geo-distributed) locations are becoming
increasingly important. However, geo-distributed DCNs are vulnerable to large-scale region failuresdue to disasters. This makes DCN protection against region failures a critical task. Proactive
protection is an important way to fight against DCN failures by network planning before disasters
occur. To this end, this thesis investigates DCN placement and data backup against region failures
via proactive protection mechanisms.

We first study optimal DCN and content placement with the objective of minimizing DCN
failure probability. In this part, we combine the probabilistic region failure model and the grid
partition scheme to capture the key features of the general non-uniform distribution of a potential
region failure (in terms of its occurring probability and intensity) and to conduct network
vulnerability assessment. Based on the vulnerability information, we further develop an integer
linear program (ILP)-based theoretical framework to achieve optimal DCN and content placementwith the minimum DCN failure probability. A heuristic is also proposed to make our solution morescalable for large-scale networks.

We then optimize data backup for a particular DCN node threatened by an upcoming disaster by
properly exploring the ε early warning time of the disaster, where ε denotes the time interval
between the earliest moment that the DCN node is aware of the disaster and the latest moment thatthe disaster indeed hits the DCN. In this part, we investigate urgent data backup within the ε early
warning time of the disaster for both homogeneous and heterogeneous data backup scenarios (theformer concerns with the scenario that different types of data are backed up to the same set ofbackup DCN nodes while the latter considers the scenario that different types of data may be backed
up to the different sets of backup DCN nodes).

In the homogeneous data backup scenario, we divide our design into two sub problems: Backup
Capacity Evaluation (BCE) and Backup Cost Minimization (BCM). BCE helps DCN operators tofind the maximum backup capacity, and thus fully utilize the early warning time to back up as muchdata as possible. Since the maximum backup capacity may not be sufficient for backing up all data,priority can be given to those more important data. On the other hand, BCM minimizes backup costby properly selecting a set of safe backup DCN nodes and routes for those more important data. We
propose both ILPs and heuristic for the two sub-problems.

In the heterogeneous data backup scenario, we propose two backup schemes: maximum data
backup scheme (MDBS) and fairness data backup scheme (FDBS). The former maximizes the total
amount of data that can be backed up, and the latter maximizes the same proportion of data backup
for each type of data in a fair manner. For each scheme, an ILP and a heuristic are proposed toproperly select a set of safe backup DCN nodes and corresponding backup routes.

Our proposed solutions for DCN and content placement can effectively protect DCNs andcontents against a potential region failure under the global non-uniform distribution. By taking theearly warning time into account, our proposed backup schemes can generate efficient solutions forurgent data backup against ε-time early warning disaster. It is expected that the study in this thesis
can provide a fundamental guideline to the design of disaster survivable DCNs.

審 査 結 果 の 要 旨This thesis focuses on the data center network (DCN) placement and data backup against
region failures. More specifically, this thesis conducts the studies on: 1) region failure-aware DCN
and content placement, 2) homogeneous data backup based on early warning of region failure, and3) heterogeneous data backup based on early warning of region failure. In the first study, this thesis
conducts network vulnerability assessment, and then provides the DCN and content placement
solutions based on the integer linear program (ILP) and heuristic to achieve the minimum DCN
failure probability. In the second study, this thesis investigates the homogeneous data backup withinthe ε early warning time of region failure due to disaster, and develops the corresponding ILP modelto achieve the maximum backup capacity and also a heuristic scheme for cost-efficient backup. In
the last study, this thesis proposes two backup schemes: maximum data backup scheme (MDBS) andfairness data backup scheme (FDBS) for heterogeneous data backup within the ε early warning timeof region failure due to disaster, and also develops the corresponding ILP model and heuristic foreach backup scheme.

・論文の構成Chapter 1 Introduction
Chapter 2 Related Work
Chapter 3 Region Failure-Aware Data Center Network and Content Placement
Chapter 4 Homogeneous Data Backup Based on Early Warning of Region Failure
Chapter 5 Heterogeneous Data Backup Based on Early Warning of Region Failure
Chapter 6 Conclusion
・研究目的の妥当性，従来の手法との比較においての有意性，および理論・実験手法の新規性
This thesis studies the data center network (DCN) protection against region failures due todisasters. More specifically, this thesis focuses on the DCN placement and data backup against
region failures and conducts the studies of: 1) region failure-aware DCN and content placement, 2)
homogeneous data backup based on early warning of region failure, and 3) heterogeneous data
backup based on early warning of region failure.

In the first work, we study the optimal DCN and content placement with the objective ofminimizing the DCN failure probability. Despite much work has been done on this topic, they failed
to take into account the realistic non-uniform distribution property of region failure and the inherent
tradeoff among failure probabilities of DCN hosting nodes, failure probabilities of requesting paths
and traffic transmission delay. To address these limitations, this thesis combines the probabilistic
region failure model and the grid partition scheme to capture the key features of the general
non-uniform distribution of a potential region failure (in terms of its occurring probability andintensity) and to conduct network vulnerability assessment. Based on the network vulnerability
information, we then develop an integer linear program (ILP)-based theoretical framework toachieve the optimal DCN and content placement solution with the minimum DCN failure probability,
where the tradeoff among failure probabilities of DCN hosting nodes, failure probabilities ofrequesting paths and traffic transmission delay is considered. A corresponding heuristic is also
proposed to make the placement problem more scalable for large-scale networks.

In the second work, we study the optimal homogeneous data backup for a particular DCN
node threatened by an upcoming disaster by properly exploring the ε early warning time of thedisaster, where ε denotes the time interval between the earliest moment that the DCN node is awareof the disaster and the latest moment that the disaster indeed hits the DCN. In this urgent databackup, different types of data will be backed up to the same set of backup DCN nodes and thefairness for each type of data is not considered. A few available works on this topic just focus on
the objectives of maximizing data owners’ utilities and the number of contents that can beevacuated. However, the backup cost, as a major concern for DCN operators to select a backup
strategy, has not been taken into account in these works. We conduct study on the urgent data
backup within the ε early warning time of region failure due to disaster to maximize the backupcapacity and minimize the overall backup cost, and develop the corresponding ILP models for
identifying the optimal data backup solutions and also the time-efficient heuristic scheme to makesuch date backup problem more scalable.

In the last work, we study the optimal heterogeneous data backup for a particular DCN nodethreatened by an upcoming disaster by properly exploring the ε early warning time of the disaster,where different types of data may be backed up to the different sets of backup DCN nodes and thefairness for each type of data is considered. We propose two backup schemes: maximum data
backup scheme (MDBS) and fairness data backup scheme (FDBS). The former maximizes the total
amount of data that can be backed up, while the latter maximizes the same proportion of data
backup for each type of data in a fair manner. For each backup scheme, an ILP and a corresponding
heuristic are proposed to properly select the set of safe backup OCN nodes and the related backup
routes for data backup.
・得られた知見のシステム情報科学の分野における意義
The results of this thesis provide the following insights.
1. The studies conducted in this thesis will be helpful for the design of disaster survivable DCNs.
The results in the study of region failure-aware DCN and content placement can provide solutions
for DCN and content placement to effectively protect DCNs and contents against a global
non-uniform distribution of potential region failure.

2. The study of urgent data backup within the early warning time of region failure due to disastersheds light on the design of urgent backup schemes for fully utilizing the early warning time of an
upcoming disaster to minimize the data loss in DCNs due to disaster.