Abstract

To quantitatively measure content connectivity and provide protection for different kinds of content, the concept of k-node (edge) content connectivity is proposed recently. Based on k-node (edge) content connectivity, k-node (edge) content connected elastic optical datacenter network (KC-EODN) is proposed to design disaster-resilient and spectrum-efficient optical datacenter networks. In KC-EODN, k independent end-to-content paths are established for each request. However, it will consume too much resource to assign dedicated spectrum for each end-to-content path. Spectrum sharing among multiple end-to-content paths of different requests can greatly improve resource efficiency. In this paper, a novel perfect matching based sharing principle among multiple end-to-content paths of different requests is proposed. Based on the new proposed sharing principle, we present the shared end-to-content backup path protection (SEBPP) scheme for KC-EODN. Integer linear program (ILP) model and heuristic algorithms are designed for SEBPP scheme with the objective of minimizing the total of working and backup spectrum resources. Numerical results show that the proposed SEBPP scheme can greatly reduce spectrum consumption while ensuring the survivability against natural disaster and multi-failures.

© 2016 Optical Society of America

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 W1 and B1 are established. As presented in Fig. 1(b), the paths W1 and B1 are assigned with different sets of contiguous FSs.

 figure: Fig. 1

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 | PPT Slide | 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 Wa and Wb are working paths and the paths Ba1, Ba2, Bb1 and Bb2 are backup paths. Path Ba1 and path Wb have common link(3,E). Path Wa and path Bb1 have common link(7,F), and path Ba2 and path Bb2 have common link(2,E). Because the traffic on working paths Wa and Wb will both switch to the common link(2,E) when link(3,E) and link(7,F) fail simultaneously, so that backup paths Ba2 and Bb2 cannot share spectrum resource on common link(2,E). In Fig. 2(c), we choose a new routing for path Bb1 and the new routing is 3→4→F. Because there does not exist resource competition for working paths Wa and Wb under random concurrent dual-failures, so that backup paths Ba2 and Bb2 can share spectrum on common link(2,E) as presented in Fig. 2(d).

 figure: Fig. 2

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 | PPT Slide | 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 Pa = {Wa, Ba1, Ba2, …, Ba(k-1)} be the set of independent end-to-content paths for request a, Wa is the end-to-content working path, {Ba1, Ba2, …, Ba(k-1)} are k-1 independent end-to-content backup paths; Pb = {Wb, Bb1, Bb2, …, Bb(k-1)} is the set of independent end-to-content paths for request b, Wb is the end-to-content working path, {Bb1, Bb2, …, Bb(k-1)} are k-1 independent end-to-content backup paths.

Sharing principle: Let Bai be ith end-to-content backup path in set Pa for request a, Bbj be jth end-to-content backup path in set Pb for request b, then Bai and Bbj can share backup resource on common links as long as there does not exist a perfect matching between set Pa/Bai and Pb/Bbj.

The perfect matching between set Pa/Bai and Pb/Bbj means that each end-to-content path in set Pa/Bai can find a corresponding shared risk end-to-content path in set Pb/Bbj, and vice versa. That is to say there exist concurrent k-1 failures which can cause all end-to-content paths in set (Pa/Bai)(Pb/Bbj) 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 Pa = {Ba1, Wa, Ba2}, Pb = {Wb, Bb1, Bb2}. Fig. 3(a) presents the risk relationship between set Pa/Ba2 and set Pb/Bb2. As presented in Fig. 3(b), there exist one perfect matching between set Pa/Ba2 and set Pb/Bb2, so that end-to-content backup paths Ba2 and Bb2 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 Pa/Ba2 and set Pb/Bb2, so that end-to-content backup paths Ba2 and Bb2 can share spectrum on common link(2,E).

 figure: Fig. 3

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 | PPT Slide | 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 Pa/Bai and Pb/Bbj. Then, PMS algorithm use Hungarian method to find perfect matching in G(X,Y,E). In the following PMS algorithm, Bax is an end-to-content path in Pa/Bai, Bby is an end-to-content path in Pb/Bbj.

Tables Icon

Algorithm 1. Perfect Matching Searching

The time complexity of Hungarian method is O((k-1)3). So, the time complexity of PMS algorithm is O((k-1)2*|E| + (k-1)3), where (k-1) is the number of end-to-content paths in set Pa/Bai or Pb/Bbj, |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 Pi that requires ni subcarriers is translated to finding a starting FS fi frequency after which it can use ni 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,…}, rR.
L ( i,j )
Length of physical link (i,j)
Lr
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
Cd
The capacity of datacenter d
K
The maximum number of replicas per content, 0<K|D|
Λ
Λ = {f1, f2, …, f|Λ|} denotes the ordered set of FSs in each fiber link
F
F = {F1, F2, …, 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)
nl,(s,c)r
The number of required FSs (including the guard bands) for lth 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{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Λ
Y(i,j)(s,c),r{0,1}
The link(i,j) with modulation level r is followed by the end-to-content working path for request (s,c)
Zr(s,c){0,1}
Modulation level r is adopted by end-to-content working path for request (s,c)
Bl,(i,j),f(s,c),r{0,1}
FS f in link(i,j) with modulation level r is used by the lth end-to-content backup path for request (s,c), l is positive integer from 1 to k-1, fΛ
Xl,(i,j)(s,c),r{0,1}
The link(i,j) with modulation level r is followed by the lth end-to-content backup path for request (s,c)
Zl,r(s,c){0,1}
Modulation level r is adopted by lth end-to-content backup path for request (s,c)
Ad(s,c),r{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
A¯l,d(s,c),r{0,1}
Datacenter d is used as the destination datacenter for request (s,c) on the lth end-to-content backup path with modulation level r
Rdc{0,1}
The replicas of content c is placed in datacenter d, dD
αx(s,c){0,1}
The end-to-content working path of request (s,c) goes through the shared risk group x, xSRG
βl,x(s,c){0,1}
The lth end-to-content backup path of request(s,c) goes through the shared risk group x, xSRG
ωx(s,c){0,1}
The end-to-content working path of request (s,c) goes through the failure x, xF
ξl,x(s,c){0,1}
The lth end-to-content backup path of request(s,c) goes through the failure x, xF
χl,(i,j),x(s,c){0,1} The working traffic will switch to the link(i,j) of the lth end-to-content backup path of request (s,c) when the other end-to-content paths are down due to shared risk group x, xF

5.1. Objective function

min((s,c)TrR(i,j)EfΛW(i,j),f(s,c),r+(i,j)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.

j:(i,j)EY(i,j)(s,c),rj:(j,i)EY(j,i)(s,c),r={Zr(s,c)i=sAd(s,c),riD0other(s,c)T,i(VD),rR
j:(i,j)EfΛW(i,j),f(s,c),rj:(j,i)EfΛW(j,i),f(s,c),r={n(s,c)ri=sn(s,c)riD0other(s,c)T,i(VD),rR
rRdDAd(s,c),r=1(s,c)T
(i,j)EY(i,j)(s,c),r(i,j)EY(j,i)(s,c),r=0(s,c)T,rR,(is&&iD)
rRY(i,j)(s,c),r1(s,c)T,(i,j)E
W(i,j),f(s,c),rY(i,j)(s,c),r(s,c)T,(i,j)E,fΛ,rR
(i,j)EY(i,j)(s,c),r*L(i,j)Lr(s,c)T,rR
rRZr(s,c)=1(s,c)T
Zr(s,c)Y(i,j)(s,c),r(s,c)T,(i,j)E
n(s,c)r=Zr(s,c)*λ(s,c)r*B(s,c)T,rR

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 variableAd(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 Zr(s,c). Equation (10) calculates the number of FSs for request (s,c) with modulation level r on the end-to-content working path.

j:(i,j)EXl,(i,j)(s,c),rj:(j,i)EXl,(j,i)(s,c),r={Zl,r(s,c)i=sA¯l,d(s,c),riD0other(s,c)T,l<k,i(VD),rR
j:(i,j)EfΛBl,(i,j),f(s,c),rj:(j,i)EfΛBl,(j,i),f(s,c),r={n(s,c),lri=sn(s,c),lriD0other(s,c)T,l<k,i(VD),rR
rRdDA¯l,d(s,c),r=1(s,c)T,l<k
(i,j)EXl,(i,j)(s,c),r(i,j)EXl,(j,i)(s,c),r=0(s,c)T,l<k,rR,(is&&iD)
rRXl,(i,j)(s,c),r1(s,c)T,l<k,(i,j)E
Bl,(i,j),f(s,c),rXl,(i,j)(s,c),r(s,c)T,l<k,(i,j)E,fΛ,rR
(i,j)EXl,(i,j)(s,c),r*L(i,j)Lr(s,c)T,rR,l<k
rRZl,r(s,c)=1(s,c)T,l<k
Zl,r(s,c)Xl,(i,j)(s,c),r(s,c)T,(i,j)E,rR,l<k
n(s,c),lr=Zl,r(s,c)*λ(s,c)r*B(s,c)T,rR,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 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 lth end-to-content backup path can only adopt one modulation level. Equation (19) sets the value of Zl,r(s,c). Equation (20) calculates the number of FSs for request (s,c) with modulation level r on the lth end-to-content backup path.

(Y(i,j)(s,c),r+l<kXl,(i,j)(s,c),r)1(s,c)T,i(V/s),rR
(i,j)EY(i,j)(s,c),r(i,j)EXl,(i,j)(s,c),r(s,c)T,l<k,rR

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.

rR(s,c)TW(i,j),f(s,c),r1(i,j)E,fΛ
j:(i,j)EW(i,j),f(s,c),rj:(j,i)EW(j,i),f(s,c),r=0(s,c)T,i(V/s),fΛ,rR
j:(i,j)EBl,(i,j),f(s,c),rj:(j,i)EBl,(j,i),f(s,c),r=0(s,c)T,l<k,i(V/s),fΛ,rR

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),rW(i,j),(f+1)(s,c),r1)×(M)f'[f+2,|Λ|]W(i,j),f'(s,c),r(s,c)T,(i,j)E,fΛ,rR
(Bl,(i,j),f(s,c),rBl,(i,j),(f+1)(s,c),r1)×(M)f'[f+2,|Λ|]Bl,(i,j),f'(s,c),r(s,c)T,l<k,(i,j)E,fΛ,rR

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

rR(Ad(s,c),r+l<kA¯l,d(s,c),r)MRdcrR(Ad(s,c),r+l<kA¯l,d(s,c),r)(s,c)T,cC,dD
dDRdcKcC.

Equation (28) sets the value ofRdcand 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.

(s,c)rRfΛW(i,j),f(s,c),r+π(i,j)|Λ|(i,j)E.
cCSc*RdcCddD

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.

rR(i,j)xY(i,j)(s,c),rNαx(s,c)rR(i,j)xY(i,j)(s,c),r(s,c)T,xSRG
rR(i,j)xXl,(i,j)(s,c),rNβl,x(s,c)rR(i,j)xXl,(i,j)(s,c),r(s,c)T,xSRG,l<k
αx(s,c)+l<kβl,x(s,c)k(s,c)T,xSRG

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.

rR(i,j)xY(i,j)(s,c),rNωx(s,c)rR(i,j)xY(i,j)(s,c),r(s,c)T,xF
rR(i,j)xXl,(i,j)(s,c),rNξl,x(s,c)rR(i,j)xXl,(i,j)(s,c),r(s,c)T,xF,l<k
χl,(i,j),x(s,c)rRXl,(i,j)(s,c),r(s,c)T,l<k,(i,j)E,xF
χl,(i,j),x(s,c)ωx(s,c)(s,c)T,l<k,(i,j)E,xF
χl,(i,j),x(s,c)1ξl,x(s,c)(s,c)T,l<k,(i,j)E,xF
χl,(i,j),x(s,c)l'<kξl',x(s,c)(k2)(s,c)T,l<k,(i,j)E,xF
χl,(i,j),x(s,c)l'<kξl',x(s,c)(k2)+rRXl,(i,j)(s,c),r+ωx(s,c)ξl,x(s,c)2(s,c)T,l<k,(i,j)E,xF
π(i,j)(s,c)l<kfΛχl,(i,j),x(s,c)*Bl,(i,j),f(s,c)xF,(i,j)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{f1, f2, …, 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.

Tables Icon

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

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), Cf 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,Bl,f denotes the set of end-to-content backup paths which pass the link l and share the FS f, Bj is one end-to-content path in Bl,f, PBj is the set of existing k end-to-content paths of the same request which Bj belong to, |PM(PBj/Bj,p_paths)|denotes the size of perfect matching betweenPBj/Bj and p_paths. Equation (44) is used to calculate the cost of each FS in SW link.

COST(l,SWP)=flCflSWP
Cf={1ifFSisfree1/(BjBl,f(k1|PM(PBj/Bj,p_paths)|)+1)ifFSisshareable,|PM(PBj/Bj,p_paths)|k1

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 ith 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.

Tables Icon

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

The time complexity of Algorithm 3 is O((k1)4*|T|*|E|*|Λ|2*|R|+(k1)*|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, (k1)3*|T|from step 15 to step 19, (k1)3*|T|*|E|*|Λ|from step 10 to step 21, |V|2*|D|from step 22 to step 31, (k1)3*|T|*|E|*|Λ|2+|V|2*|D|*|Λ|from step 9 to step 35, (k1)4*|T|*|E|*|Λ|2*|R|+(k1)*|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(k1)4*|T|2*|E|*|Λ|2*|R|+(k1)*|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.

 figure: Fig. 4

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

Download Full Size | PPT Slide | PDF

Tables Icon

Table 1. Parameters for Three Kinds of Modulation Levels

Tables Icon

Table 2. Requests used in ILP model

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.

 figure: Fig. 5

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 | PPT Slide | 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.

 figure: Fig. 6

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

Download Full Size | PPT Slide | 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.

 figure: Fig. 7

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 | PPT Slide | PDF

 figure: Fig. 8

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

Download Full Size | PPT Slide | 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}.

 figure: Fig. 9

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

Download Full Size | PPT Slide | 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.

 figure: Fig. 10

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 | PPT Slide | 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]  

References

  • View by:

  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]

2016 (1)

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]

2015 (2)

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]

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).

2014 (2)

2013 (2)

2012 (1)

2011 (1)

2009 (1)

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]

2007 (2)

2004 (1)

2000 (1)

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]

1957 (1)

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

Bose, S. K.

Cai, A.

Cao, J.

Christodoulopoulos, K.

Dikbiyik, F.

Grover, W. D.

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]

Gu, W.

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]

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]

Guo, B.

Guo, L.

Habib, M. F.

Huang, S.

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]

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]

Jin, Z.

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]

Jinno, M.

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]

Kozicki, B.

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]

Leenheer, M. D.

Li, L.

Li, X.

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]

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]

Liu, M.

Ma, C.

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]

Matsuoka, S.

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]

Mukherjee, B.

Munkres, J.

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

Ou, C.

Peng, L.

Sahasrabuddhe, L. H.

Shen, G.

Shi, Y.

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]

Sone, Y.

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]

Stamatelakis, D.

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]

Takara, H.

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]

Tomkos, I.

Tornatore, M.

Tsukishima, Y.

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]

Varvarigos, E. A.

Wang, C.

Wang, Y.

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]

Wei, X.

Wei, Y.

Yin, M.

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]

Yin, S.

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]

Yu, H.

Zang, H.

Zhang, J.

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]

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]

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]

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]

Zhang, M.

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]

Zhao, Y.

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]

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]

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]

Zhou, Y.

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]

Zukerman, M.

IEEE Commun. Lett. (1)

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]

IEEE Commun. Mag. (1)

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]

IEEE Trans. Commun. (1)

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]

J. Lightwave Technol. (8)

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]

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]

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).

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]

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]

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]

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]

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]

J. Opt. Commun. Netw. (1)

J. Soc. Ind. Appl. Math. (1)

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

Opt. Express (1)

Photonic Netw. Commun. (1)

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]

Other (8)

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]

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]

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]

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]

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

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]

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]

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]

Cited By

Optica participates in Crossref's Cited-By Linking service. Citing articles from Optica Publishing Group journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (10)

Fig. 1
Fig. 1 Two independent end-to-content paths in elastic optical datacenter network (a) routing and modulation level and (b) spectrum allocation.
Fig. 2
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.
Fig. 3
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.
Fig. 4
Fig. 4 Simulation topology (a) n6s8 with the length of all links, (b) n6s8 with SRG1, and (c) n6s8 with SRG2.
Fig. 5
Fig. 5 The spectrum efficiency of SEBPP and DEBPP when k = 3 (a) distance-adaptive RMLSA and (b) RMLSA with lowest modulation level.
Fig. 6
Fig. 6 The spectrum efficiency of SEBPP and DEBPP when k = 3 (a) SRG1-disjoint RMLSA and (b) SRG2-disjoint RMLSA.
Fig. 7
Fig. 7 The spectrum efficiency of SEBPP and DEBPP when k = 2 (a) distance-adaptive RMLSA and (b) RMLSA with lowest modulation level.
Fig. 8
Fig. 8 The spectrum efficiency of SEBPP and DEBPP when k = 2 (a) SRG1-disjoint RMLSA and (b) SRG2-disjoint RMLSA.
Fig. 9
Fig. 9 Simulation topology (a) NSFNet with the length of all links and (b) NSFNet with SRGs.
Fig. 10
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.

Tables (5)

Tables Icon

Algorithm 1. Perfect Matching Searching

Tables Icon

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

Tables Icon

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

Tables Icon

Table 1 Parameters for Three Kinds of Modulation Levels

Tables Icon

Table 2 Requests used in ILP model

Equations (45)

Equations on this page are rendered with MathJax. Learn more.

min ( ( s , c ) T r R ( i , j ) E f Λ W ( i , j ) , f ( s , c ) , r + ( i , j ) E π ( i , j ) )
j : ( i , j ) E Y ( i , j ) ( s , c ) , r j : ( j , i ) E Y ( j , i ) ( s , c ) , r = { Z r ( s , c ) i = s A d ( s , c ) , r i D 0 o t h e r ( s , c ) T , i ( V D ) , r R
j : ( i , j ) E f Λ W ( i , j ) , f ( s , c ) , r j : ( j , i ) E f Λ W ( j , i ) , f ( s , c ) , r = { n ( s , c ) r i = s n ( s , c ) r i D 0 o t h e r ( s , c ) T , i ( V D ) , r R
r R d D A d ( s , c ) , r = 1 ( s , c ) T
( i , j ) E Y ( i , j ) ( s , c ) , r ( i , j ) E Y ( j , i ) ( s , c ) , r = 0 ( s , c ) T , r R , ( i s & & i D )
r R Y ( i , j ) ( s , c ) , r 1 ( s , c ) T , ( i , j ) E
W ( i , j ) , f ( s , c ) , r Y ( i , j ) ( s , c ) , r ( s , c ) T , ( i , j ) E , f Λ , r R
( i , j ) E Y ( i , j ) ( s , c ) , r * L ( i , j ) L r ( s , c ) T , r R
r R Z r ( s , c ) = 1 ( s , c ) T
Z r ( s , c ) Y ( i , j ) ( s , c ) , r ( s , c ) T , ( i , j ) E
n ( s , c ) r = Z r ( s , c ) * λ ( s , c ) r * B ( s , c ) T , r R
j : ( i , j ) E X l , ( i , j ) ( s , c ) , r j : ( j , i ) E X l , ( j , i ) ( s , c ) , r = { Z l , r ( s , c ) i = s A ¯ l , d ( s , c ) , r i D 0 o t h e r ( s , c ) T , l < k , i ( V D ) , r R
j : ( i , j ) E f Λ B l , ( i , j ) , f ( s , c ) , r j : ( j , i ) E f Λ B l , ( j , i ) , f ( s , c ) , r = { n ( s , c ) , l r i = s n ( s , c ) , l r i D 0 o t h e r ( s , c ) T , l < k , i ( V D ) , r R
r R d D A ¯ l , d ( s , c ) , r = 1 ( s , c ) T , l < k
( i , j ) E X l , ( i , j ) ( s , c ) , r ( i , j ) E X l , ( j , i ) ( s , c ) , r = 0 ( s , c ) T , l < k , r R , ( i s & & i D )
r R X l , ( i , j ) ( s , c ) , r 1 ( s , c ) T , l < k , ( i , j ) E
B l , ( i , j ) , f ( s , c ) , r X l , ( i , j ) ( s , c ) , r ( s , c ) T , l < k , ( i , j ) E , f Λ , r R
( i , j ) E X l , ( i , j ) ( s , c ) , r * L ( i , j ) L r ( s , c ) T , r R , l < k
r R Z l , r ( s , c ) = 1 ( s , c ) T , l < k
Z l , r ( s , c ) X l , ( i , j ) ( s , c ) , r ( s , c ) T , ( i , j ) E , r R , l < k
n ( s , c ) , l r = Z l , r ( s , c ) * λ ( s , c ) r * B ( s , c ) T , r R , l < k
( Y ( i , j ) ( s , c ) , r + l < k X l , ( i , j ) ( s , c ) , r ) 1 ( s , c ) T , i ( V / s ) , r R
( i , j ) E Y ( i , j ) ( s , c ) , r ( i , j ) E X l , ( i , j ) ( s , c ) , r ( s , c ) T , l < k , r R
r R ( s , c ) T W ( i , j ) , f ( s , c ) , r 1 ( i , j ) E , f Λ
j : ( i , j ) E W ( i , j ) , f ( s , c ) , r j : ( j , i ) E W ( j , i ) , f ( s , c ) , r = 0 ( s , c ) T , i ( V / s ) , f Λ , r R
j : ( i , j ) E B l , ( i , j ) , f ( s , c ) , r j : ( j , i ) E B l , ( j , i ) , f ( s , c ) , r = 0 ( s , c ) T , l < k , i ( V / s ) , f Λ , r R
( W ( i , j ) , f ( s , c ) , r W ( i , j ) , ( f + 1 ) ( s , c ) , r 1 ) × ( M ) f ' [ f + 2 , | Λ | ] W ( i , j ) , f ' ( s , c ) , r ( s , c ) T , ( i , j ) E , f Λ , r R
( B l , ( i , j ) , f ( s , c ) , r B l , ( i , j ) , ( f + 1 ) ( s , c ) , r 1 ) × ( M ) f ' [ f + 2 , | Λ | ] B l , ( i , j ) , f ' ( s , c ) , r ( s , c ) T , l < k , ( i , j ) E , f Λ , r R
r R ( A d ( s , c ) , r + l < k A ¯ l , d ( s , c ) , r ) M R d c r R ( A d ( s , c ) , r + l < k A ¯ l , d ( s , c ) , r ) ( s , c ) T , c C , d D
d D R d c K c C .
( s , c ) r R f Λ W ( i , j ) , f ( s , c ) , r + π ( i , j ) | Λ | ( i , j ) E .
c C S c * R d c C d d D
r R ( i , j ) x Y ( i , j ) ( s , c ) , r N α x ( s , c ) r R ( i , j ) x Y ( i , j ) ( s , c ) , r ( s , c ) T , x S R G
r R ( i , j ) x X l , ( i , j ) ( s , c ) , r N β l , x ( s , c ) r R ( i , j ) x X l , ( i , j ) ( s , c ) , r ( s , c ) T , x S R G , l < k
α x ( s , c ) + l < k β l , x ( s , c ) k ( s , c ) T , x S R G
r R ( i , j ) x Y ( i , j ) ( s , c ) , r N ω x ( s , c ) r R ( i , j ) x Y ( i , j ) ( s , c ) , r ( s , c ) T , x F
r R ( i , j ) x X l , ( i , j ) ( s , c ) , r N ξ l , x ( s , c ) r R ( i , j ) x X l , ( i , j ) ( s , c ) , r ( s , c ) T , x F , l < k
χ l , ( i , j ) , x ( s , c ) r R X l , ( i , j ) ( s , c ) , r ( s , c ) T , l < k , ( i , j ) E , x F
χ l , ( i , j ) , x ( s , c ) ω x ( s , c ) ( s , c ) T , l < k , ( i , j ) E , x F
χ l , ( i , j ) , x ( s , c ) 1 ξ l , x ( s , c ) ( s , c ) T , l < k , ( i , j ) E , x F
χ l , ( i , j ) , x ( s , c ) l ' < k ξ l ' , x ( s , c ) ( k 2 ) ( s , c ) T , l < k , ( i , j ) E , x F
χ l , ( i , j ) , x ( s , c ) l ' < k ξ l ' , x ( s , c ) ( k 2 ) + r R X l , ( i , j ) ( s , c ) , r + ω x ( s , c ) ξ l , x ( s , c ) 2 ( s , c ) T , l < k , ( i , j ) E , x F
π ( i , j ) ( s , c ) l < k f Λ χ l , ( i , j ) , x ( s , c ) * B l , ( i , j ) , f ( s , c ) x F , ( i , j ) E
COST ( l , S W P ) = f l C f l S W P
C f = { 1 if FS is free 1/ ( B j 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 ) | k 1

Metrics