Shared end-to-content backup path protection in k-node (edge) content connected elastic optical datacenter networks

Xin Li; Shanguo Huang; Shan Yin; Bingli Guo; Yongli Zhao; Jie Zhang; Min Zhang; Wanyi Gu

doi:10.1364/OE.24.009446

1. Introduction

With the frequent occurrence of natural disaster and human-made intentional attacks on datacenter networks, the survivability of datacenter networks is attracting more and more attention [1]. The traditional survivability techniques mainly rely on network connectivity to achieve traffic uninterrupted transmission. Restoration mechanisms make best effort to establish recovery paths for interrupted working flows after failures. Protection mechanisms reserve backup resources which can be organized into pre-configured structure such as P-Cycle, P-Polyhedron, etc., for working flows [2,3]. It can also be classified into dedicated protection and shared protection. Dedicated protection only assigns pre-configured structure to specified working traffic, but shared protection allows multiple backup paths sharing the spectrum resource on common links as long as their working paths do not fail simultaneously. Compared with dedicated protection, shared protection has higher spectrum efficiency [4]. Note that network connectivity has a fixed value for a given topology, the connectivity between users and one particular datacenter can be easily destroyed by multi-failures or natural disaster. Nevertheless, the data/services can be replicated and maintained in multiple datacenters. The user can obtain the data/services from any reachable datacenter regardless of where it is located. Even if multi-failures or natural disaster break the datacenter network into several disconnected parts, the data/services will not be interrupted as long as there exist one reachable datacenter in each part. This new type of connectivity is called content connectivity which is defined as the reachability of content from any point of a datacenter network [5]. Content connectivity is designed for datacenter networks. It no longer merely ensures the connectivity between source-destination nodes pair but guarantees the connectivity between user and the content. In order to quantitatively measure content connectivity and provide protection for different kinds of content, we propose the concept of k-node (edge) content connectivity [6]. The datacenter network which satisfies k-node (edge) content connectivity requirement is called k-node (edge) content connected datacenter network. Anycast is a network addressing and routing methodology in which datagrams from a single sender are routed to the topologically nearest node in a group of potential receivers [7]. The differences between k-node (edge) content connectivity and anycast include three aspects. The first is that anycast is a network addressing and routing methodology, but k-node (edge) content connectivity is a network protection technology. The second is that each user in k-node (edge) content connected network has at least k independent end-to-content paths to access the content, but anycast can't guarantee that. The third is that anycast is designed for IP network and is usually implemented by using border gateway protocol, but k-node (edge) content connectivity is designed for optical datacenter networks and can be implemented by using software defined network. Based on orthogonal frequency-division multiplexing (OFDM) technology, elastic optical network (EON) which can allocate the number of frequency slots (FSs) according to the size of traffic has higher spectrum efficiency than traditional fixed-grid optical networks [8]. Based on k-node (edge) content connectivity, k-node (edge) content connected elastic optical datacenter network (KC-EODN) is proposed and studied in this paper for higher spectrum efficiency while ensuring the survivability against multi-failures and natural disaster. In KC-EODN, we establish k independent end-to-content paths for each request. Nevertheless, it will consume too much resource to allocate dedicated spectrum for all end-to-content paths. Shared protection which has higher spectrum efficiency is more suitable for KC-EODN. In this paper, a new sharing principle among multiple end-to-content backup paths of different requests is proposed. Based on the proposed sharing principle, the shared end-to-content backup path protection (SEBPP) scheme is designed to improve the spectrum efficiency of KC-EODN. The problem of provisioning end-to-content working and backup paths in SEBPP scheme is solved through Integer Linear Program (ILP) and heuristic algorithms. The rest of this paper is organized as follows. Section II discusses the related works and our contributions. Section III and section IV describe the network model and the SEBPP scheme. The ILP model and heuristic algorithms are presented in section V and section VI. The performance of the proposed ILP model and heuristic algorithms are presented and discussed in section VII. Finally, section VIII concludes this paper.

2. Related works and our contributions

2.1. Content connectivity

Content connectivity was first proposed in [5], the authors gave the definition of content connectivity and designed a survivable virtual network mapping to maintain failure-resilient content connectivity in multi-layer optical datacenter networks. In [9], a disaster-aware dynamic content placement algorithm was proposed to minimize the required number of replicas of content while satisfying content connectivity requirement through probabilistic disaster model. In [10], content connectivity combined with bandwidth-adaptability was proposed to reduce the spectrum consumption. The concept of k-node (edge) content connectivity was proposed in [6]. ILP model was proposed to design k-node (edge) content connected optical datacenter network. In [11], we proposed a flexible content placement algorithm and demonstrated content placement through SDN-enabled OTN and IP networks.

2.2. Shared backup path protection (SBPP)

SBPP has obtained extensive studies. The existing research can be divided into three categories: improving resource efficiency, efficient working path and backup path computation, and SBPP against multi-failures. The research of improving resource efficiency is mainly carried out in flexible optical WDM (FWDM) networks and elastic optical networks (EON). In [12], an efficient survivable flexible optical WDM network design algorithm was proposed. In [13], an elastic separate-protection-at-connection (ESPAC) scheme was proposed for EON. In [14], ILP model for SBPP scheme in EON was proposed with the objective of minimizing both the required spare capacity and the maximum number of frequency slots used. In [15], protection path based hitless spectrum defragmentation algorithms were proposed to improve the spectrum utilization with SBPP. In [16], conservative and aggressive backup sharing policies were proposed and evaluated in EON. In [17], distance adaptive dynamic routing and spectrum allocation algorithms were proposed for SBPP scheme to maximize spare capacity sharing among multiple backup light-paths. In [18], an enhanced shared backup path protection (ESBPP) scheme was proposed to provide the complete survivability for double-link failures. In [19], a partial SRLG-disjoint protection (PSDP) scheme was proposed to tolerate the single-SRLG failure. In [20], the connection availability of SRLG-based shared path protection was calculated in WDM mesh networks.

2.3. Our contributions

Our contributions consist of three aspects.

1) We apply k-node (edge) content connectivity into elastic optical datacenter network and propose the disaster-resilient and spectrum-efficient KC-EODN.
2) We propose the sharing principle among multiple end-to-content backup paths of different requests. We transform determining two end-to-content backup paths can share spectrum resource on common links or not into searching perfect matching between two end-to-content path sets. Based on the new sharing principle, SEBPP scheme is designed for KC-EODN.
3) We develop an ILP model for SEBPP scheme with the objective of minimizing the total working and backup spectrum resources. In ILP model, we scan all possible failures to calculate the maximum needed backup spectrum in each link. Heuristic algorithms are also designed to achieve RMLSA for end-to-content working path and backup paths.

3. Network model

In this section, the definition and theoretical basis of k-node (edge) content connectivity is introduced. With tunable transponder at each source node, the routing and spectrum allocation for end-to-content paths is described.

3.1. K-node (edge) content connectivity and KC-EODN

The concept of k-node (edge) content connectivity is proposed to design disaster-resilient optical datacenter network and provide protection for different kinds of content. Reference [6] gives the definition of the k-node (edge) content connectivity that there does not exist a set of k-1 nodes (edges) whose removal disconnects the connectivity from any remaining node to the content. Theoretical analysis shows that achieving k-node (edge) content connectivity is equivalent to searching k independent end-to-content paths between source node and multiple datacenters where the content is hosted for each request. The datacenter network which satisfies k-node (edge) content connectivity requirement is called k-node (edge) content connected datacenter network. We apply k-node (edge) content connectivity into elastic optical datacenter network and propose the KC-EODN to design disaster-resilient and spectrum-efficient optical datacenter network.

3.2. Independent end-to-content paths in KC-EODN

In KC-EODN, we need to address the problem of routing, modulation level and spectrum allocation (RMLSA) for each end-to-content path. The modulation levels such as BPSK, QPSK, 8QAM, etc., affect the Quality of Transmission (QoT) and the transmission distance of end-to-content path [21]. The optical OFDM signal with higher modulation level will have shorter transmission reach. The spectrum can also affect the QoT and can influence the resource efficiency of the KC-EODN. The RMLSA for each end-to-content path must satisfy spectrum contiguity and spectrum continuity requirements [14]. The whole spectrum in each fiber link is composed of a continuous frequency slots (FSs) with a step of constant small spectrum F Hz, irrespectively of the modulation level.

We assume that the transponder at each source node is tunable, so that any end-to-content path can use different sets of contiguous FSs. As presented in Fig. 1(a), the content is replicated and maintained in datacenter E and datacenter F. For Req-1, two independent end-to-content paths W₁ and B₁ are established. As presented in Fig. 1(b), the paths W₁ and B₁ are assigned with different sets of contiguous FSs.

Fig. 1 Two independent end-to-content paths in elastic optical datacenter network (a) routing and modulation level and (b) spectrum allocation.

Download Full Size | PDF

4. SEBPP scheme

In this section, we give an example of spectrum sharing between two requests. Then, the perfect matching searching (PMS) algorithm which is used to determine two end-to-content backup paths can share spectrum resource on common links or not is also proposed.

4.1. The problem of spectrum sharing among multiple end-to-content backup paths

The sharing principle of the traditional SBPP scheme is that multiple backup paths can share spectrum resource on common links as long as their working paths do not fail simultaneously. The sharing principle of the SEBPP scheme in KC-EODN becomes more complicated because the sharing among multiple end-to-content paths is determined not only by their working paths but also by the other end-to-content backup paths of the same request.

In Fig. 2(a), the content is placed in datacenter E and datacenter F. We establish three independent end-to-content paths for each request.The paths W_a and W_b are working paths and the paths B_a₁, B_a₂, B_b₁ and B_b₂ are backup paths. Path B_a₁ and path W_b have common link(3,E). Path W_a and path B_b₁ have common link(7,F), and path B_a₂ and path B_b₂ have common link(2,E). Because the traffic on working paths W_a and W_b will both switch to the common link(2,E) when link(3,E) and link(7,F) fail simultaneously, so that backup paths B_a₂ and B_b₂ cannot share spectrum resource on common link(2,E). In Fig. 2(c), we choose a new routing for path B_b₁ and the new routing is 3→4→F. Because there does not exist resource competition for working paths W_a and W_b under random concurrent dual-failures, so that backup paths B_a₂ and B_b₂ can share spectrum on common link(2,E) as presented in Fig. 2(d).

Fig. 2 Spectrum sharing between end-to-content backup paths (a) routing and modulation level without spectrum sharing, (b) spectrum allocation without spectrum sharing, (c) routing and modulation level with spectrum sharing, and (d) spectrum allocation with spectrum sharing.

Download Full Size | PDF

4.2. Sharing principle

SEBPP scheme allows multiple end-to-content backup paths to share spectrum resource on common links as long as the other end-to-content paths including working path and backup paths of the same requests do not fail simultaneously. Let P_a = {W_a, B_a₁, B_a₂, …, B_a₍_k_-1)} be the set of independent end-to-content paths for request a, W_a is the end-to-content working path, {B_a₁, B_a₂, …, B_a₍_k_-1)} are k-1 independent end-to-content backup paths; P_b = {W_b, B_b₁, B_b₂, …, B_b₍_k_-1)} is the set of independent end-to-content paths for request b, W_b is the end-to-content working path, {B_b₁, B_b₂, …, B_b₍_k_-1)} are k-1 independent end-to-content backup paths.

Sharing principle: Let B_ai be i_th end-to-content backup path in set P_a for request a, B_bj be j_th end-to-content backup path in set P_b for request b, then B_ai and B_bj can share backup resource on common links as long as there does not exist a perfect matching between set P_a/B_ai and P_b/B_bj.

The perfect matching between set P_a/B_ai and P_b/B_bj means that each end-to-content path in set P_a/B_ai can find a corresponding shared risk end-to-content path in set P_b/B_bj, and vice versa. That is to say there exist concurrent k-1 failures which can cause all end-to-content paths in set (P_a/B_ai) $\cup$ (P_b/B_bj) fail simultaneously. Perfect matching leads to resource competition on common links of end-to-content backup paths under concurrent multiple failures.

The sets of independent end-to-content paths for Req-a and Req-b in Fig. 2(a) are P_a = {B_a1, W_a, B_a2}, P_b = {W_b, B_b1, B_b2}. Fig. 3(a) presents the risk relationship between set P_a/B_a2 and set P_b/B_b2. As presented in Fig. 3(b), there exist one perfect matching between set P_a/B_a2 and set P_b/B_b2, so that end-to-content backup paths B_a2 and B_b2 cannot share spectrum resource on common link(2,E). Then, we take the independent end-to-content paths in Fig. 2(c) as an example. Fig. 3(c) presents the risk relationship. As presented in Fig. 3(d), there does not exist perfect matching between set P_a/B_a2 and set P_b/B_b2, so that end-to-content backup paths B_a2 and B_b2 can share spectrum on common link(2,E).

Fig. 3 Sharing principle between path sets (a) risk relationship, (b) perfect matching, (c) risk relationship without perfect matching, and (d) spectrum sharing on common link.

Download Full Size | PDF

4.3. Perfect matching searching algorithm

We present the perfect matching searching (PMS) algorithm to find perfect matching between two end-to-content path sets. In graph theory, there exist a good perfect matching searching algorithm named Hungarian method which was developed in 1955 by Harold Kuhn [22]. PMS algorithm first construct the bipartite graph G(X,Y,E) between P_a/B_ai and P_b/B_bj. Then, PMS algorithm use Hungarian method to find perfect matching in G(X,Y,E). In the following PMS algorithm, B_ax is an end-to-content path in P_a/B_ai, B_by is an end-to-content path in P_b/B_bj.

Algorithm 1. Perfect Matching Searching

View Table | View all tables in this article

The time complexity of Hungarian method is O((k-1)³). So, the time complexity of PMS algorithm is O((k-1)²*|E| + (k-1)³), where (k-1) is the number of end-to-content paths in set P_a/B_ai or P_b/B_bj, |E| is the number of links in KC-EODN.

5. Problem formulation

In this section, the SEBPP scheme is realized through ILP model. The objective of ILP model is minimizing the total of working and backup spectrum resources consumed by all end-to-content paths. In ILP model, we assume that each transponder at source node can be tuned to utilize any number of FSs forming a continuous spectrum with a step of F Hz. The establishment of an end-to-content path P_i that requires n_i subcarriers is translated to finding a starting FS f_i frequency after which it can use n_i contiguous FSs (including the guard bands). The ILP model obtains the optimal content placement which guarantees that there exist k independent end-to-content paths for each request and the spectrum resources consumed by all end-to-content paths is minimized. We formally state the ILP model as follows:

G(V,D,E)	Elastic optical datacenter network, V represents the set of nodes, D represents the set of datacenters, E represents the set of links
SRG	Set of shared risk groups
B	Base capacity of a FS with single bit per symbol modulation (BPSK)
R	Set of modulation levels, R = {1,2,3,…}, r $\in$ R.
L ₍ _i,j ₎	Length of physical link (i,j)
L_r	Maximum optical transmission reach of a light-path adopting modulation level r
C	Set of content
T	Set of request (s,c), where s is the source node, c is the content
$λ_{(s, c)}$	The traffic demand for source node s for content c
C_d	The capacity of datacenter d
K	The maximum number of replicas per content, $0 < K \leq \| D \|$
$Λ$	_$Λ$ = {f₁, f₂, …, $f_{\| Λ \|}$ } denotes the ordered set of FSs in each fiber link
F	_{F = {}_F_1, _F_2, …, _Fm_} denotes the possible failures in G(V,D,E)
$n_{(s, c)}^{r}$	The number of required FSs (including the guard bands) for end-to-content working path with modulation level r for request (s,c)
$n_{l, (s, c)}^{r}$	The number of required FSs (including the guard bands) for l_th end-to-content backup path with modulation level r for request (s,c)
$π_{(i, j)}$	The total spectrum in link(i,j) used for end-to-content backup paths
$W_{(i, j), f}^{(s, c), r} \in {0, 1}$	FS f in link(i,j) with modulation level r is used by the end-to-content working path for request (s,c), $f \in Λ$
$Y_{(i, j)}^{(s, c), r} \in {0, 1}$	The link(i,j) with modulation level r is followed by the end-to-content working path for request (s,c)
$Z_{r}^{(s, c)} \in {0, 1}$	Modulation level r is adopted by end-to-content working path for request (s,c)
$B_{l}_{, (i, j), f}^{(s, c), r} \in {0, 1}$	FS f in link(i,j) with modulation level r is used by the l_th end-to-content backup path for request (s,c), l is positive integer from 1 to k-1, $f \in Λ$
$X_{l}_{, (i, j)}^{(s, c), r} \in {0, 1}$	The link(i,j) with modulation level r is followed by the l_th end-to-content backup path for request (s,c)
$Z_{l, r}^{(s, c)} \in {0, 1}$	Modulation level r is adopted by l_th end-to-content backup path for request (s,c)
$A_{d}^{(s, c), r} \in {0, 1}$	Datacenter d is used as the destination datacenter for request (s,c) on the end-to-content working path with modulation level r
${\bar{A}}_{l, d}^{(s, c), r} \in {0, 1}$	Datacenter d is used as the destination datacenter for request (s,c) on the l_th end-to-content backup path with modulation level r
$R_{d}^{c} \in {0, 1}$	The replicas of content c is placed in datacenter d, d $\in$ D
$α_{x}^{(s, c)} \in {0, 1}$	The end-to-content working path of request (s,c) goes through the shared risk group x, x $\in$ SRG
$β_{l, x}^{(s, c)} \in {0, 1}$	The l_th end-to-content backup path of request(s,c) goes through the shared risk group x, x $\in$ SRG
$ω_{x}^{(s, c)} \in {0, 1}$	The end-to-content working path of request (s,c) goes through the failure x, x $\in$ F
$ξ_{l, x}^{(s, c)} \in {0, 1}$	The l_th end-to-content backup path of request(s,c) goes through the failure x, x $\in$ F
$χ_{l, (i, j), x}^{(s, c)} \in {0, 1}$	The working traffic will switch to the link(i,j) of the l_th end-to-content backup path of request (s,c) when the other end-to-content paths are down due to shared risk group x, x $\in$ F

5.1. Objective function

\min (\sum_{(s, c) \in T} \sum_{r \in R} \sum_{(i, j) \in E} \sum_{f \in Λ} W_{(i, j), f}^{(s, c), r} + \sum_{(i, j) \in E} π_{(i, j)})

The objective function sums all consumed working and backup spectrum resources consumed by all end-to-content paths of all requests. Its target is to minimize the total spectrum consumption.

\sum_{j : (i, j) \in E} Y_{(i, j)}^{(s, c), r} - \sum_{j : (j, i) \in E} Y_{(j, i)}^{(s, c), r} \begin{matrix} = & {\begin{matrix} Z_{r}^{(s, c)} & i = s \\ - A_{d}^{(s, c), r} & i \in D \\ 0 & o t h e r \end{matrix} \begin{matrix} \begin{matrix} \forall (s, c) \end{matrix} \in T, \end{matrix} \forall i \in (V \cup D) \end{matrix}, r \in R

\sum_{j : (i, j) \in E} \sum_{f \in Λ} W_{(i, j), f}^{(s, c), r} - \sum_{j : (j, i) \in E} \sum_{f \in Λ} W_{(j, i), f}^{(s, c), r} = {\begin{matrix} n_{(s, c)}^{r} & i = s \\ - n_{(s, c)}^{r} & i \in D \\ 0 & o t h e r \end{matrix} \begin{matrix} \forall (s, c) \end{matrix} \in T, \forall i \in (V \cup D), r \in R

\sum_{r \in R} \sum_{d \in D} A_{d}^{(s, c), r} = 1 \begin{matrix} \forall (s, c) \end{matrix} \in T

\sum_{(i, j) \in E} Y_{(i, j)}^{(s, c), r} - \sum_{(i, j) \in E} Y_{(j, i)}^{(s, c), r} = 0 \begin{matrix} \begin{matrix} \forall (s, c) \end{matrix} \in T, r \in R \end{matrix}, \forall (i \neq s & & i \notin D)

\sum_{r \in R} Y_{(i, j)}^{(s, c), r} \leq 1 \begin{matrix} \begin{matrix} \forall (s, c) \in T, \forall (i, j) \end{matrix} \in E \end{matrix}

W_{(i, j), f}^{(s, c), r} \leq Y_{(i, j)}^{(s, c), r} \begin{matrix} \begin{matrix} \forall (s, c) \end{matrix} \in T, \end{matrix} \forall (i, j) \in E, \forall f \in Λ, r \in R

\sum_{(i, j) \in E} Y_{(i, j)}^{(s, c), r} * L_{(i, j)} \leq L_{r} \begin{matrix} \forall (s, c) \end{matrix} \in T, \forall r \in R

\sum_{r \in R} Z_{r}^{(s, c)} = 1 \begin{matrix} \forall (s, c) \end{matrix} \in T

Z_{r}^{(s, c)} \geq Y_{(i, j)}^{(s, c), r} \begin{matrix} \forall (s, c) \end{matrix} \in T, \forall (i, j) \in E

n_{(s, c)}^{r} = \begin{matrix} Z_{r}^{(s, c)} * ⌈ \frac{λ_{(s, c)}}{r * B} ⌉ & \forall (s, c) \end{matrix} \in T, \forall r \in R

Equation (1) ensures that for request (s,c), only one end-to-content working path can be followed and the traffic demand cannot be split. Equation (2) enforces flow conservation on the end-to-content working path. This constraint guarantees that the number of outgoing FSs is equal to the number of incoming FSs for each end-to-content path except source node and destination datacenter. The destination datacenter which is represented by variable $A_{d}^{(s, c)}$ for each end-to-content working path is not fixed. Equation (3) ensures that only one datacenter is assigned per end-to-content working path. Equation (4) ensures that each end-to-content working path obeys modulation level consecutiveness constraint. Equation (5) ensures that the end-to-content working path can only adopt one modulation level. Equation (6) ensures that only the FSs on link(i, j) which is used to route request (s,c) can be allocated. Equation (7) ensures that the path length of end-to-content working path with modulation level r cannot greater than the maximum optical transmission reach of modulation level r. Equation (8) ensures that the end-to-content working path can only adopt one modulation level. Equation (9) sets the value of $Z_{r}^{(s, c)}$ . Equation (10) calculates the number of FSs for request (s,c) with modulation level r on the end-to-content working path.

\sum_{j : (i, j) \in E} X_{l, (i, j)}^{(s, c), r} - \sum_{j : (j, i) \in E} X_{l, (j, i)}^{(s, c), r} \begin{matrix} = & {\begin{matrix} Z_{l, r}^{(s, c)} & i = s \\ - {\bar{A}}_{l, d}^{(s, c), r} & i \in D \\ 0 & o t h e r \end{matrix} \begin{matrix} \begin{matrix} \forall (s, c) \end{matrix} \in T, \end{matrix} \begin{matrix} \forall l < k \end{matrix}, \forall i \in (V \cup D) \end{matrix}, r \in R

\sum_{j : (i, j) \in E} \sum_{f \in Λ} B_{l, (i, j), f}^{(s, c), r} - \sum_{j : (j, i) \in E} \sum_{f \in Λ} B_{l, (j, i), f}^{(s, c), r} = {\begin{matrix} n_{(s, c), l}^{r} & i = s \\ - n_{(s, c), l}^{r} & i \in D \\ 0 & o t h e r \end{matrix} \begin{matrix} \forall (s, c) \end{matrix} \in T, \begin{matrix} \forall l < k \end{matrix}, \forall i \in (V \cup D), r \in R

\sum_{r \in R} \sum_{d \in D} {\bar{A}}_{l, d}^{(s, c), r} = 1 \begin{matrix} \begin{matrix} \forall (s, c) \end{matrix} \in T, \forall l < k \end{matrix}

\sum_{(i, j) \in E} X_{l, (i, j)}^{(s, c), r} - \sum_{(i, j) \in E} X_{l, (j, i)}^{(s, c), r} = 0 \begin{matrix} \begin{matrix} \forall (s, c) \end{matrix} \in T, \forall l < k, r \in R \end{matrix}, \forall (i \neq s & & i \notin D)

\sum_{r \in R} X_{l, (i, j)}^{(s, c), r} \leq 1 \begin{matrix} \begin{matrix} \forall (s, c) \in T, \forall l < k, \forall (i, j) \end{matrix} \in E \end{matrix}

B_{l, (i, j), f}^{(s, c), r} \leq X_{l, (i, j)}^{(s, c), r} \begin{matrix} \begin{matrix} \forall (s, c) \end{matrix} \in T, \end{matrix} \begin{matrix} \forall l < k \end{matrix}, \forall (i, j) \in E, \forall f \in Λ, r \in R

\sum_{(i, j) \in E} X_{l, (i, j)}^{(s, c), r} * L_{(i, j)} \leq L_{r} \begin{matrix} \forall (s, c) \end{matrix} \in T, \forall r \in R, \forall l < k

\sum_{r \in R} Z_{l, r}^{(s, c)} = 1 \begin{matrix} \forall (s, c) \end{matrix} \in T, \forall l < k

Z_{l, r}^{(s, c)} \geq X_{l, (i, j)}^{(s, c), r} \begin{matrix} \forall (s, c) \end{matrix} \in T, \forall (i, j) \in E, r \in R, \forall l < k

n_{(s, c), l}^{r} = \begin{matrix} Z_{l, r}^{(s, c)} * ⌈ \frac{λ_{(s, c)}}{r * B} ⌉ & \forall (s, c) \end{matrix} \in T, \forall r \in R, \forall l < k

Equation (11) ensures that for request (s,c), the traffic demand on each end-to-content backup path cannot be split. Equation (12) enforces flow conservation on k-1 independent end-to-content backup paths. The destination datacenter which is represented by variable ${\bar{A}}_{l, d}^{(s, c)}$ for each end-to-content backup path is not fixed. Equation (13) ensures that only one datacenter is assigned per end-to-content backup path. Equation (14) ensures that each end-to-content backup path obeys modulation level consecutiveness constraint. Equation (15) ensures that the end-to-content backup path can only adopt one modulation level. Equation (16) ensures that only the FSs on link(i, j) which is used to route request (s,c) can be allocated. Equation (17) ensures that the path length of end-to-content backup path with modulation level r cannot greater than the maximum optical transmission reach of modulation level r. Equation (18) ensures that the l_th end-to-content backup path can only adopt one modulation level. Equation (19) sets the value of $Z_{l, r}^{(s, c)}$ . Equation (20) calculates the number of FSs for request (s,c) with modulation level r on the l_th end-to-content backup path.

(Y_{(i, j)}^{(s, c), r} + \sum_{l < k} X_{l, (i, j)}^{(s, c), r}) \leq 1 \begin{matrix} \begin{matrix} \begin{matrix} \forall (s, c) \end{matrix} \in T, \forall i \in (V / s) \end{matrix} \end{matrix}, \forall r \in R

\sum_{(i, j) \in E} Y_{(i, j)}^{(s, c), r} \leq \sum_{(i, j) \in E} X_{l, (i, j)}^{(s, c), r} \begin{matrix} \begin{matrix} \forall (s, c) \end{matrix} \in T, \forall l < k \end{matrix}, \forall r \in R

Equation (21) ensures that the k end-to-content paths including working path and backup paths are independent so that they do not have any internal node in common. Equation (22) ensures that the end-to-content working path is the shortest path among k independent end-to-content paths.

\sum_{r \in R} \sum_{(s, c) \in T} W_{(i, j), f}^{(s, c), r} \leq 1 \begin{matrix} \begin{matrix} \forall (i, j) \end{matrix} \in E, \forall f \in Λ \end{matrix}

\sum_{j : (i, j) \in E} W_{(i, j), f}^{(s, c), r} - \sum_{j : (j, i) \in E} W_{(j, i), f}^{(s, c), r} = 0 \begin{matrix} \begin{matrix} \forall (s, c) \in T \end{matrix} \end{matrix}, i \in (V / s), \forall f \in Λ, \forall r \in R

\sum_{j : (i, j) \in E} B_{l,}_{(i, j), f}^{(s, c), r} - \sum_{j : (j, i) \in E} B_{l}_{, (j, i), f}^{(s, c), r} = 0 \begin{matrix} \begin{matrix} \forall (s, c) \in T \end{matrix} \end{matrix}, \forall l < k, i \in (V / s), \forall f \in Λ, \forall r \in R

Equation (23) ensures that a FS in one link can only be assigned to one request. Equation (24) ensures that all links along the end-to-content working path employ the same set of FSs. Equation (25) ensures that all links along the end-to-content backup path employ the same set of FSs.

(W_{(i, j), f}^{(s, c), r} - W_{(i, j), (f + 1)}^{(s, c), r} - 1) \times (- M) \geq \sum_{f' \in [f + 2, | Λ |]} W_{(i, j), f'}^{(s, c), r} \forall (s, c) \in T, \forall (i, j) \in E, \forall f \in Λ, \forall r \in R

(B_{l,}_{(i, j), f}^{(s, c), r} - B_{l,}_{(i, j), (f + 1)}^{(s, c), r} - 1) \times (- M) \geq \sum_{f' \in [f + 2, | Λ |]} B_{l,}_{(i, j), f'}^{(s, c), r} \forall (s, c) \in T, \forall l < k, \forall (i, j) \in E, \forall f \in Λ, \forall r \in R

Equation (26) and Eq. (27) ensures that the FSs are consecutive in each link of end-to-content working path and backup path.

\frac{\sum_{r \in R} (A_{d}^{(s, c), r} + \sum_{l < k} {\bar{A}}_{l, d}^{(s, c), r})}{M} \leq R_{d}^{c} \leq \sum_{r \in R} (A_{d}^{(s, c), r} + \sum_{l < k} {\bar{A}}_{l, d}^{(s, c), r}) \begin{matrix}  \end{matrix} \begin{matrix} \begin{matrix} \forall (s, c) \in T, \forall c \end{matrix} \in C, \begin{matrix} \forall d \end{matrix} \in D \end{matrix}

\sum_{d \in D} R_{d}^{c} \leq K \begin{matrix} \begin{matrix} \begin{matrix} \forall c \end{matrix} \in C \end{matrix} \end{matrix} .

Equation (28) sets the value of $R_{d}^{c}$ and ensures that content c is replicated and placed in datacenter d if and only if datacenter d is assigned as destination datacenter for one end-to-content working path or backup path. Here, M is a large integer constant. Equation (29) constrains the number of replicas per content.

\sum_{(s, c)} \sum_{r \in R} \sum_{f \in Λ} W_{(i, j), f}^{(s, c), r} + π_{(i, j)} \leq | Λ | \begin{matrix} \begin{matrix} \begin{matrix} \begin{matrix} \begin{matrix} \forall (i, j) \in E \end{matrix} \end{matrix} \end{matrix} \end{matrix} \end{matrix} .

\sum_{c \in C} S_{c} * R_{d}^{c} \leq C_{d} \begin{matrix} \begin{matrix} \forall d \end{matrix} \in D \end{matrix}

Equation (30) ensures that the total number of FSs used for all end-to-content paths including working paths and backup paths through a link does not exceed the link’s capacity. Equation (31) ensures that the total size of content placed on one datacenter for all requests does not exceed its capacity.

\frac{\sum_{r \in R} \sum_{(i, j) \in x} Y_{(i, j)}^{(s, c), r}}{N} \leq α_{x}^{(s, c)} \leq \sum_{r \in R} \sum_{(i, j) \in x} Y_{(i, j)}^{(s, c), r} \begin{matrix} \forall (s, c) \end{matrix} \in T, \forall x \in S R G

\frac{\sum_{r \in R} \sum_{(i, j) \in x} X_{l, (i, j)}^{(s, c), r}}{N} \leq β_{l, x}^{(s, c)} \leq \sum_{r \in R} \sum_{(i, j) \in x} X_{l, (i, j)}^{(s, c), r} \begin{matrix} \forall (s, c) \end{matrix} \in T, \forall x \in S R G, \forall l < k

α_{x}^{(s, c)} + \sum_{l < k} β_{l, x}^{(s, c)} \leq k \begin{matrix} \forall (s, c) \end{matrix} \in T, x \in S R G

Equation (32) sets the value of $α_{l, x}^{(s, c)}$ , N is a large integer constant. Equation (33) sets the value of $β_{l, x}^{(s, c)}$ . Equation (34) ensures the SRG-disjoint property of k-node (node) content connectivity where one disaster does not destroy all k end-to-content paths.

\frac{\sum_{r \in R} \sum_{(i, j) \in x} Y_{(i, j)}^{(s, c), r}}{N} \leq ω_{x}^{(s, c)} \leq \sum_{r \in R} \sum_{(i, j) \in x} Y_{(i, j)}^{(s, c), r} \begin{matrix} \forall (s, c) \end{matrix} \in T, \forall x \in F

\frac{\sum_{r \in R} \sum_{(i, j) \in x} X_{l, (i, j)}^{(s, c), r}}{N} \leq ξ_{l, x}^{(s, c)} \leq \sum_{r \in R} \sum_{(i, j) \in x} X_{l, (i, j)}^{(s, c), r} \begin{matrix} \forall (s, c) \end{matrix} \in T, \forall x \in F, \forall l < k

χ_{l, (i, j), x}^{(s, c)} \leq \sum_{r \in R} X_{l, (i, j)}^{(s, c), r} \begin{matrix} \begin{matrix} \begin{matrix} \forall (s, c) \in T, \forall l < k, \forall (i, j) \in E \end{matrix} \end{matrix} \end{matrix}, \forall x \in F

χ_{l, (i, j), x}^{(s, c)} \leq ω_{x}^{(s, c)} \begin{matrix} \begin{matrix} \begin{matrix} \forall (s, c) \in T, \forall l < k, \forall (i, j) \in E, \forall x \in F \end{matrix} \end{matrix} \end{matrix}

χ_{l, (i, j), x}^{(s, c)} \leq 1 - ξ_{l, x}^{(s, c)} \begin{matrix}  \end{matrix} \forall (s, c) \in T, \forall l < k, \forall (i, j) \in E, \forall x \in F

χ_{l, (i, j), x}^{(s, c)} \leq \frac{\sum_{l' < k} ξ_{l', x}^{(s, c)}}{(k - 2)} \forall (s, c) \in T, \forall l < k, \forall (i, j) \in E, \forall x \in F

χ_{l, (i, j), x}^{(s, c)} \geq \frac{\sum_{l' < k} ξ_{l', x}^{(s, c)}}{(k - 2)} + \sum_{r \in R} X_{l, (i, j)}^{(s, c), r} + ω_{x}^{(s, c)} - ξ_{l, x}^{(s, c)} - 2 \forall (s, c) \in T, \forall l < k, \forall (i, j) \in E, \forall x \in F

π_{(i, j)} \geq \sum_{(s, c)} \sum_{l < k} \sum_{f \in Λ} χ_{l, (i, j), x}^{(s, c)} * B_{l, (i, j), f}^{(s, c)} \forall x \in F, \forall (i, j) \in E

Equation (35) sets the value of $ω_{x}^{(s, c)}$ , N is a large integer constant. Equation (36) sets the value of $ξ_{l, x}^{(s, c)}$ . Equation (37) ensures that only the link in each-to-content backup paths can be used for protection switching. Equation (38) ensures that protection switching can be carried out only when the end-to-content working path fails. Equation (39) ensures that the link in each end-to-content backup path can be used for protection switching only when the disaster event x does not go through this link. Equation (40) ensures that only one end-to-content path can be used for protection switching. Equation (41) ensures that link(i,j) can be used for protection switching when it satisfy the Eqs. (35)-(40). Equation (42) bounds the number of FSs used in a link for shared protection according to the proposed sharing principle.

6. Heuristic algorithms

In this section, we first introduce the concepts of spectrum window (SW) and spectrum window plane (SWP). Then, heuristic algorithms based on SWP are proposed to achieve RMLSA for end-to-content working and backup paths.

6.1. RMLSA for end-to-content working paths in SEBPP scheme

SW in each fiber link represents a certain number of continuous FSs [23]. For request (s,c) with n needed FSs, the fiber link with FSs set{f₁, f₂, …, $f_{| Λ |}$ } contains a total of $| Λ |$ -n + 1 SWs. The elastic optical datacenter network can be split into multiple SWPs. In each plane, a virtual link between a pair of nodes is connected if the SW in the corresponding fiber link is available [17]. The RMLSA algorithm for end-to-content working path first scans the whole set of SWPs, and then scans the whole set of datacenters in each SWP to find the shortest end-to-content path. In Algorithm 2, w_path indicates the end-to-content working path with shortest distance, w_index indicates the index of assigned FSs, W₍_s,c₎ represents the path with shortest distance in current SWP, W₍_s,d₎ represents shortest path between source node s and datacenter d in current SWP, ST represents the total of SWPs, R = {8QAM, QPSK, BPSK} represents the optional modulation levels.

Algorithm 2. RMLSA for end-to-content working path with shortest distance

View Table | View all tables in this article

The time complexity of Algorithm 2 is O( ${| V |}^{2} * | D | * | Λ | * | R |$ ), where $| V |$ is the number of node, $| D |$ is the number of datacenters, $| Λ |$ is the maximum number of SWPs, $| R |$ is the number of modulation levels. The Algorithm 2 is guaranteed to run in polynomial time.

6.2. RMLSA for end-to-content backup paths in SEBPP scheme

Once the end-to-content working path is successfully obtained, then we need to search k-1 independent end-to-content backup paths of the same request. Each available SW link in SWP has a cost which indicates the degree of sharing among multiple end-to-content backup paths of different requests. The SEBPP scheme updates this cost once one end-to-content path is abtained. An SW link is considered available only if all the contained FSs are free or shareable. In Eq. (43), C_f denotes the cost of FS f. Equation (43) is used to calculate the cost of each link in SWP. In Eq. (44), p_paths denotes the set of already obtained end-to-content paths including working path and backup paths of the same request, $B_{l, f}$ denotes the set of end-to-content backup paths which pass the link l and share the FS f, B_j is one end-to-content path in $B_{l, f}$ , $P_{B_{j}}$ is the set of existing k end-to-content paths of the same request which B_j belong to, $| P M_{(P_{B_{j}} / B_{j}, p_p a t h s)} |$ denotes the size of perfect matching between $P_{B_{j}} / B_{j}$ and p_paths. Equation (44) is used to calculate the cost of each FS in SW link.

COST (l, S W P) = \sum_{f \in l_{}} C_{f} \begin{matrix} \forall l \in S W P \end{matrix}

C_{f} = {\begin{matrix} \begin{matrix} 1 & if FS is free \end{matrix} \\ \begin{matrix} 1/ (\sum_{B_{j} \in B_{l, f}} (k - 1 - | P M_{(P_{B_{j}} / B_{j}, p_p a t h s)} |) + 1) & if FS is shareable, | P M_{(P_{B_{j}} / B_{j}, p_p a t h s)} | \neq k - 1 \end{matrix} \end{matrix}

In Algorithm 3, b_paths represents the set of k-1 end-to-content backup path in G(V,E,D), b_paths_i is i_th end-to-content backup path, b_indexs is the set of startindexs of k-1 end-to-content backup path, b_indexs_i is startindex of end-to-content backup path b_paths_i, B₍_s,c₎ represents the end-to-content backup path with minimal cost in current SWP, B₍_s,d₎ represents the end-to-content backup path with minimal cost between source node s and datacenter d in current SWP, ST represents the total of SWPs in G(V,E,D), R = {8QAM, QPSK, BPSK} represents all optional modulation levels.

Algorithm 3. RMLSA for end-to-content backup path with maximum sharing

View Table | View all tables in this article

The time complexity of Algorithm 3 is O( ${(k - 1)}^{4} * | T | * | E | * {| Λ |}^{2} * | R | + {(k - 1)}^{} * {| V |}^{2} * | D | * | Λ | * | R |$ ), where $| T |$ is the total number of requests, (k-1) is the number of end-to-content backup paths, $| V |$ is the number of nodes in G(V,E,D), $| E |$ is the number of links in G(V,E,D), $| D |$ is the number of datacenters, $| Λ |$ is the maximum number of SWPs, $| R |$ is the number of all optional modulation levels. The following analyses of time complexity are under the worst case. The time complexity is $| T |$ from step 12 to step 14, ${(k - 1)}^{3} * | T |$ from step 15 to step 19, ${(k - 1)}^{3} * | T | * | E | * | Λ |$ from step 10 to step 21, ${| V |}^{2} * | D |$ from step 22 to step 31, ${(k - 1)}^{3} * | T | * | E | * {| Λ |}^{2} + {| V |}^{2} * | D | * {| Λ |}^{}$ from step 9 to step 35, ${(k - 1)}^{4} * | T | * | E | * {| Λ |}^{2} * | R | + {(k - 1)}^{} * {| V |}^{2} * | D | * | Λ | * | R |$ from step 1 to step 39, The Algorithm 3 is guaranteed to run in polynomial time. And at worst, the time complexity of all requests is ${(k - 1)}^{4} * {| T |}^{2} * | E | * {| Λ |}^{2} * | R | + (k - 1) * | T | * {| V |}^{2} * | D | * | Λ | * | R |$ .

7. Performance evaluation

We evaluate the performance of the proposed SEBPP scheme through ILP model and heuristic algorithms. The simulations of ILP model are conducted on small n6e8 network, and simulations are conducted on NSFNet for heuristic algorithms.

7.1. SEBPP scheme through ILP model

As presented in Fig. 4,we assume that each link has 20 FSs, each content occupies 1G storage resource and we do not consider the datacenter’s capacity limitation. The requests are generated according to the uniform distribution offline in advance. To simplify the computational complexity, we only consider two modulation levels (BPSK and QPSK) in ILP model. The spectrum efficiency, data rate per subcarrier and transmission reach of two modulation levels are listed in Table 1. The transmission rate of each request are listed in Table 2. The ILP model is implemented by using Java in ILOG CPLEX V12.5. The computer in our simulations is configured with an Intel Core i5 3.3 GHz CPU and 8 Gb RAM.

Fig. 4 Simulation topology (a) n6s8 with the length of all links, (b) n6s8 with SRG1, and (c) n6s8 with SRG2.

Download Full Size | PDF

Table 1. Parameters for Three Kinds of Modulation Levels

View Table | View all tables in this article

Table 2. Requests used in ILP model

View Table | View all tables in this article

We compare the spectrum efficiency of SEBPP scheme with dedicated end-to-content backup path protection (DEBPP) scheme in KC-EODN. We need to establish three independent end-to-content paths for each request. In DEBPP scheme, the FSs on common link of one end-to-content backup path cannot be shared with other end-to-content paths. Fig. 5(a) shows the spectrum consumption of SEBPP scheme and DEBPP scheme with distance-adaptive RMLSA. The results show that SEBPP scheme can reduce about 15% spectrum consumption than DEBPP scheme. Fig. 5(b) shows the spectrum consumption of SEBPP scheme and DEBPP scheme with lowest modulation level RMLSA (BPSK in this paper). Obviously, the distance-adaptive SEBPP scheme has the best spectrum efficiency. When the number of requests exceeds four, the ILP model of DEBPP scheme with lowest modulation level has no solution, so Fig. 5(b) only gives the spectrum consumption with four requests. This phenomenon also indicates that distance-adaptive SEBPP scheme can accommodate more requests and improve the spectrum efficiency of KC-EODN.

Fig. 5 The spectrum efficiency of SEBPP and DEBPP when k = 3 (a) distance-adaptive RMLSA and (b) RMLSA with lowest modulation level.

Download Full Size | PDF

We also evaluate the spectrum efficiency of SEBPP scheme with SRG constraint. Fig. 6(a) and Fig. 6(b) show the spectrum consumption of SEBPP scheme and DEBPP scheme with SRG1 and SRG2 respectively. Fig. 6(a) show that the spectrum consumption of SEBPP scheme with SRG1 is less than the spectrum consumption of SEBPP scheme with no SRG. The spectrum consumption of DEBPP scheme with SRG1 is very close to the spectrum consumption of DEBPP scheme with no SRG. That because all end-to-content paths of the same request are independent, so the SRG constraint has litter influence on spectrum consumption of DEBPP scheme. But for SEBPP scheme, the sharing among multiple requests must consider the SRG and the spectrum consumption will increase.

Fig. 6 The spectrum efficiency of SEBPP and DEBPP when k = 3 (a) SRG1-disjoint RMLSA and (b) SRG2-disjoint RMLSA.

Download Full Size | PDF

Fig. 7 shows the spectrum efficiency of SEBPP scheme and DEBPP scheme in two-node (edge) content connected elastic optical datacenter network. We need to establish two independent end-to-content paths for each request. Fig. 8 shows the spectrum consumption of SEBPP scheme and DEBPP scheme with SRG constraint. The results in Fig. 7 and Fig. 8 also show that the distance-adaptive SEBPP scheme has highest spectrum efficiency.

Fig. 7 The spectrum efficiency of SEBPP and DEBPP when k = 2 (a) distance-adaptive RMLSA and (b) RMLSA with lowest modulation level.

Download Full Size | PDF

Fig. 8 The spectrum efficiency of SEBPP and DEBPP when k = 2 (a) SRG1-disjoint RMLSA and (b) SRG2-disjoint RMLSA.

Download Full Size | PDF

7.2. SEBPP scheme through heuristic algorithms

We assume that each fiber link in NSFnet consists of 80 FSs and each source node is equipped with tunable transponder which can use different sets of contiguous FSs (Fig. 9). We assume that each content occupies 1G storage resource and we do not consider the datacenter’s capacity limitation. The heuristic algorithms adopt three modulation level listed in Table 1. The requests are generated at each source node according to a uniform distribution. The transmission rate of each request is selected from the set {40 Gbps, 100 Gbps, and 400 Gbps}.

Fig. 9 Simulation topology (a) NSFNet with the length of all links and (b) NSFNet with SRGs.

Download Full Size | PDF

We evaluate the spectrum efficiency of SEBPP scheme and DEBPP scheme in large-scale NSFNet with two RMLSA strategies: SWP-based RMLSA and Fi-Fi-based RMLSA (First fit RMLSA). Fig. 10(a) shows the spectrum consumption of SEBPP scheme and DEBPP scheme with SWP-based RMLSA and Fi-Fi-based RMLSA in three-node (edge) content connected elastic optical datacenter network. The results show that SWP-based RMLSA has better spectrum efficiency than Fi-Fi-based RMLSA. Because DEBPP scheme with Fi-Fi-based RMLSA has lowest success rate in Fig. 10(b), so the spectrum consumption of DEBPP scheme with SWP-based RMLSA is higher than DEBPP scheme with Fi-Fi-based RMLSA when the requests number is 100. The results in Fig. 10(a) show that SEBPP scheme with SWP-based RMLSA can reduce about 13% spectrum consumption than DEBPP scheme when k = 3. The results in Fig. 10(c) show that SEBPP scheme with SWP-based RMLSA can reduce about 5% spectrum consumption than DEBPP scheme when k = 2. Compared Fig. 10(a) with Fig. 10(c), the SEBPP scheme with SWP-based RMLSA has higher spectrum efficiency when the value of k is larger.

Fig. 10 The comparison between SEBPP and DEBPP (a) spectrum efficiency when k = 3, (b) success rate when k = 3, (c) spectrum efficiency k = 2, and (d) success rate when k = 2.

Download Full Size | PDF

8. Conclusions

The proposed k-node (edge) content connectivity provides an effective metric for content connected elastic optical datacenter networks. KC-EODN provides a new research direction for designing disaster-resilient and spectrum-efficient datacenter networks. SEBPP scheme can greatly improves the spectrum efficiency of elastic optical datacenter networks while ensuring the survivability against multi-faults and natural disaster. Heuristic algorithms are more flexible and have better performance in large-scale optical datacenter networks.

Acknowledgment

Parts of this work are accepted by OFC, CA, USA, 2016. This work is supported in part by the National Natural Science Foundation of China (NSFC, Nos. 61331008 and 61571058), the Hi-Tech Research and Development Program of China (863 Program) (No. 2012AA011302), the Program for New Century Excellent Talents in University (NCET-12-0793), and the Beijing Nova Program (No. 2011065).

References and links

1. M. F. Habib, M. Tornatore, M. D. Leenheer, F. Dikbiyik, and B. Mukherjee, “Design of Disaster-Resilient Optical Datacenter Networks,” J. Lightwave Technol. 30(16), 2563–2573 (2012). [CrossRef]

2. D. Stamatelakis and W. D. Grover, “Theoretical Underpinnings for the Efficiency of Restorable Networks Using Preconfigured Cycles (p-cycles),” IEEE Trans. Commun. 48(8), 1262–1265 (2000). [CrossRef]

3. S. Huang, B. Guo, X. Li, J. Zhang, Y. Zhao, and W. Gu, “Pre-configured polyhedron based protection against multi-link failures in optical mesh networks,” Opt. Express 22(3), 2386–2402 (2014). [CrossRef] [PubMed]

4. C. Ou, J. Zhang, H. Zang, L. H. Sahasrabuddhe, and B. Mukherjee, “New and Improved Approaches for Shared-Path Protection in WDM Mesh Networks,” J. Lightwave Technol. 22(5), 1223–1232 (2004). [CrossRef]

5. M. F. Habib, M. Tornatore, and B. Mukherjee, “Fault-Tolerant Virtual Network Mapping to Provide Content Connectivity in Optical Networks,” in Proceedings of Optical Fiber Communication Conference and Exposition (OFC2013), paper OTh3E.4. [CrossRef]

6. X. Li, S. Huang, S. Yin, Y. Zhou, M. Zhang, Y. Zhao, J. Zhang, and W. Gu, “Design of K-Node (Edge) Content Connected Optical Datacenter Networks,” IEEE Commun. Lett. 20(3), 466–469 (2016). [CrossRef]

7. J. Abley and K. Lindqvist, “Operation of Anycast Services,” IETF RFC 4786 (2011), https://tools.ietf.org/html/rfc4786

8. M. Jinno, H. Takara, B. Kozicki, Y. Tsukishima, Y. Sone, and S. Matsuoka, “Spectrum-efficient and scalable elastic optical path network: architecture, benefits, and enabling technologies,” IEEE Commun. Mag. 47(11), 66–73 (2009). [CrossRef]

9. S. Ferdousi, F. Dikbiyik, M. F. Habib, M. Tornatore, and B. Mukherjee, “Disaster-Aware Dynamic Content Placement in Optical Cloud Networks,” in Proceedings of Optical Fiber Communication Conference and Exposition (OFC2014), paper M2H.4. [CrossRef]

10. C. Ma, J. Zhang, Y. Zhao, Z. Jin, Y. Shi, Y. Wang, and M. Yin, “Bandwidth-adaptability protection with content connectivity against disaster in elastic optical datacenter networks,” Photonic Netw. Commun. 30(2), 309–320 (2015). [CrossRef]

11. X. Li, S. Huang, S. Yin, Y. Zhou, H. Huang, Y. Zhao, and J. Zhang, “Experimental Demonstration of Flexible Content Placement to Provide K-Content Connectivity in SDN-Enabled Data Center Optical Networks,” in Proceedings of Asia Communications and Photonics Conference (ACP2015), paper AM1H.6. [CrossRef]

12. A. N. Patel, P. N. Ji, P. Jason, and T. Wang, “Survivable Transparent Flexible Optical WDM (FWDM) Networks,” in Proceedings of Optical Fiber Communication Conference and Exposition (OFC2011), paper OTuI2. [CrossRef]

13. M. Liu, M. Tornatore, and B. Mukherjee, “Survivable Traffic Grooming in Elastic Optical Networks Shared Protection,” J. Lightwave Technol. 31(6), 903–909 (2013). [CrossRef]

14. G. Shen, Y. Wei, and S. K. Bose, “Optimal Design for Shared Backup Path Protected Elastic Optical Networks Under Single-Link Failure,” J. Opt. Commun. Netw. 6(7), 649–659 (2014). [CrossRef]

15. C. Wang, G. Shen, B. Chen, and L. Peng, “Protection Path-based Hitless Spectrum Defragmentation in Elastic Optical Networks: Shared Backup Path Protection,” in Proceedings of Optical Fiber Communication Conference and Exposition (OFC2015), paper W1I.7. [CrossRef]

16. X. Shao, Y. K. Yeo, Z. Xu, X. Cheng, and L. Zhou, “Shared-Path Protection in OFDM-based Optical Networks with Elastic Bandwidth Allocation,” in Proceedings of Optical Fiber Communication Conference and Exposition (OFC2012), paper OTh4B.4. [CrossRef]

17. C. Wang, G. Shen, and S. K. Bose, “Distance Adaptive Dynamic Routing and Spectrum Allocation in Elastic Optical Networks With Shared Backup Path Protection,” J. Lightwave Technol. 33(14), 2955–2964 (2015).

18. L. Guo, L. Li, J. Cao, H. Yu, and X. Wei, “On Finding Feasible Solutions With Shared Backup Resources for Surviving Double-Link Failures in Path-Protected WDM Mesh Networks,” J. Lightwave Technol. 25(1), 287–296 (2007). [CrossRef]

19. L. Guo and L. Li, “A Novel Survivable Routing Algorithm With Partial Shared-Risk Link Groups (SRLG)-Disjoint Protection Based on Differentiated Reliability Constraints in WDM Optical Mesh Networks,” J. Lightwave Technol. 25(6), 1410–1415 (2007). [CrossRef]

20. H. Zhang, X. Zheng, Y. Li, and H. Zhang, “Availability Analysis of Shared Backup Path Protection Subject to SRLG Constraints in WDM Mesh Networks,” in Proceedings of European Conference and Exhibition on Optical Communications (ECOC2010), paper Mo.2.D.5. [CrossRef]

21. K. Christodoulopoulos, I. Tomkos, and E. A. Varvarigos, “Elastic Bandwidth Allocation in Flexible OFDM-Based Optical Networks,” J. Lightwave Technol. 29(9), 1354–1366 (2011). [CrossRef]

22. J. Munkres, “Algorithms for the Assignment and Transportation Problems,” J. Soc. Ind. Appl. Math. 5(1), 32–38 (1957). [CrossRef]

23. A. Cai, G. Shen, L. Peng, and M. Zukerman, “Novel node-arc model and multiiteration heuristics for static routing and spectrum assignment in elastic optical networks,” J. Lightwave Technol. 31(21), 3402–3413 (2013). [CrossRef]


Input: P_a/B_ai and P_b/B_bj
Output: Perfect matching between P_a/B_ai and P_b/B_bj
1:	set G(X,Y,E), X = P_a/B_ai, Y = P_b/B_bj, E = $ϕ$
2:	for each B_ax in X do
3:		for each B_by in Y do
4:			if B_ax has common links with B_by
5:				add a link between B_ax and B_by in E
6:			end if
7:		end for
8:	end for
9:	using Hungarian method to find perfect matching in G(X,Y,E)


Input: request (s,c)
Output: w_path, w_index
1:	for each modulation level r $\in$ R (from the highest to lowest level) do
2:		$n = ⌈ \frac{λ_{(s, c)}}{r * B} ⌉$
3:		set W₍ _s,c ₎ = Null, W₍ _s,d ₎ = Null, $i n d e x_{(s, c, n)}^{}$ = Null
4:		initialize ST with $\| Λ \|$ -n + 1 SWPs of which each has n FSs
5:		for each SWP $\in$ ST (from the lowest to highest index) do
6:			remove links whose SWs are not avaialbe, and remove all unavailable datacenters
7:			for each datacenter d in datacenters set D do
8:				find the shortest s→d route W₍ _s,d ₎ using Dijkstras’s algorithm in current SWP
9:				if (W₍ _s,d ₎ $\neq$ Null&&W₍ _s,d ₎ is shorter than the transmission reach of current r)
10:					if (W₍ _s,c ₎ = = Null)
11:						W₍ _s,c ₎ = W₍ _s,d ₎
12:					else if (W₍ _s,d ₎ is shorter than W₍ _s,c ₎)
13:						W₍ _s,c ₎ = W₍ _s,d ₎
14:					end if
15:				end if
16:			end for
17:			if (W₍ _s,c ₎ $\neq$ Null)
18:				if (w_path = = Null)
19:					w_path = W₍ _s,c ₎, w_index = startindex of current SWP
20:				else if (W₍ _s,c ₎ is shorter than w_path)
21:					w_path = W₍ _s,c ₎, w_index = startindex of current SWP
22:				end if
23:			end if
24:		end for
25:		if (w_path $\neq$ Null)
26:			return w_path and w_index
27:		end if
28:	end for


Input: request (s,c), w_path
Output: b_paths, b_indexs
1:	for each i=1:(k-1) do
2:		for each modulation level r $\in$ R (from the highest to lowest level) do
3:			$n = ⌈ \frac{λ_{(s, c)}}{r * B} ⌉$
4:			set p_paths = w_path, B(s,d)= Null
5:			initialize ST with $\| Λ \|$ -n + 1 SWPs of which each has n FSs
6:			remove all the links which belong to w_path and remove all unavailable datacenters
7:			set b_paths_i = $ϕ$ , b_indexs_i = $ϕ$
8:			remove all the the links which belong to existing end-to-content paths in p_paths
9:			for each SWP $\in$ ST (from the lowest to highest index) do
10:				for each FS f in link l in current SWP
11:					obtain the end-to-content backup paths set $B_{l, f}$ of which each end-to-content path passes the link l and share the FS f
12:					for each end-to-content backup path B_j in $B_{l, f}$
13:						obtain the paths set $P_{B_{j}}$ of the same request which B_j belongs to
14:					end for
15:					for each B_j in $B_{l, f}$
16:						if ( $\| P M_{(P_{B_{j}} / B_{j}, p_p a t h s)} \|$ = = k-1)
17:							remove all the links belong to B_j from current SWP
18:						end if
19:					end for
20:					update the cost of each shareable link using Eq. (43)
21:				end for
22:				for each datacenter d in datacenters set D do
23:					find the shortest s→d route B₍ _s,d ₎ using Dijkstras’s algorithm
24:					if (B₍ _s,d ₎ $\neq$ Null&&B₍ _s,d ₎ is shorter than the transmission reach of current r)
25:						if (B₍ _s,c ₎ = = Null)
26:							B₍ _s,c ₎ = B₍ _s,d ₎
27:						else if (B₍ _s,d ₎ is less cost than B₍ _s,c ₎)
28:							B₍ _s,c ₎ = B₍ _s,d ₎
29:						end if
30:					end if
31:				end for
32:				if (B₍ _s,c ₎ $\neq$ Null)
33:					b_paths_i = B₍ _s,c ₎, b_indexs_i = startindex of current SWP, goto step37
34:				end if
35:			end for
36:		end for
37:		p_paths = p_paths $\cup$ b_paths_i, b_indexs = b_indexs $\cup$ b_indexs_i
38:	end for
39:	b_paths = p_paths / w_path
40:	return b_paths and b_indexs

	Requests
Node_1	(1,C₁,40 G), (1,C₂,100 G)
Node_2	(2,C₃,40 G), (2,C₄,100 G)
Node_3	(3,C₅,40 G), (3,C₆,100 G)
Node_4	(4,C₇,40 G), (4,C₈,100 G)


Input: P_a/B_ai and P_b/B_bj
Output: Perfect matching between P_a/B_ai and P_b/B_bj
1:	set G(X,Y,E), X = P_a/B_ai, Y = P_b/B_bj, E = $ϕ$
2:	for each B_ax in X do
3:		for each B_by in Y do
4:			if B_ax has common links with B_by
5:				add a link between B_ax and B_by in E
6:			end if
7:		end for
8:	end for
9:	using Hungarian method to find perfect matching in G(X,Y,E)

Shared end-to-content backup path protection in k-node (edge) content connected elastic optical datacenter networks

Abstract

1. Introduction

2. Related works and our contributions

2.1. Content connectivity

2.2. Shared backup path protection (SBPP)

2.3. Our contributions

3. Network model

3.1. K-node (edge) content connectivity and KC-EODN

3.2. Independent end-to-content paths in KC-EODN

4. SEBPP scheme

4.1. The problem of spectrum sharing among multiple end-to-content backup paths

4.2. Sharing principle

4.3. Perfect matching searching algorithm

5. Problem formulation

5.1. Objective function

6. Heuristic algorithms

6.1. RMLSA for end-to-content working paths in SEBPP scheme

6.2. RMLSA for end-to-content backup paths in SEBPP scheme

7. Performance evaluation

7.1. SEBPP scheme through ILP model

7.2. SEBPP scheme through heuristic algorithms

8. Conclusions

Acknowledgment

References and links

Cited By

Figures (10)

Tables (5)

Equations (45)

Optics Express

Modulation Level	Spectrum Efficiency (bps/Hz)	Data Rate per Subcarrier (Gbps)	Transmission Reach (km)
BPSK	1	12.5	2000
QPSK	2	25	1000
QAM	3	37.5	500

Modulation Level	Spectrum Efficiency (bps/Hz)	Data Rate per Subcarrier (Gbps)	Transmission Reach (km)
BPSK	1	12.5	2000
QPSK	2	25	1000
QAM	3	37.5	500