Resource sharing strategies: Which sharing to better protect primary shortest paths?

Abstract

With the widespread use of real-time applications (VoIP, IPTV, Video conference, etc.) in Internet, protection and resource optimization become increasingly desired. Network protection aims to decrease the interruption time of communications by precomputing backup paths capable to receive and route traffics of affected primary paths upon failures. Resource optimization is achieved by improving data routing and resource sharing: data routing is often optimized by following the shortest paths whereas resource sharing is applied between the backup paths protecting against different failure risks. Two strategies of resource sharing are defined in literature: (1) backup sharing which limits the resource sharing to the backup paths and (2) global sharing which extends the resource sharing to the primary and backup paths.

In this paper, we compared the effects of resource sharing strategies on the resource utilization when the primary paths correspond to the shortest ones according to a static metric. With the single failure assumption, we show formally that the resource sharing between primary and backup paths is limited to some few links which cannot form a backup path. Thus, independently of the amount of resources (for instance: bandwidth) that can be shared between the primary and backup paths, the maximum number of backup paths is bounded. In our simulation, we comfort our formal result by showing that the two strategies have close acceptance rates of backup paths and protection bandwidth utilizations.

Keywords

Routing backup path local path protection resource sharing shortest paths MPLS virtual networks

1. Introduction

Most of today’s applications (IPTV, videoconferences, VoIP, etc.) are very sensitive to the disruption of communications and consume more and more resources (such as bandwidth). Hence, protection against failures is becoming very desirable to prevent or reduce the disruption time of communications. In addition, since path protection consumes network resources if backup paths are pre-configured and their resource reserved, resource optimization is required to improve the network resource utilization.

Network protection [1,15,23,27,30] maintains the communication service continuity by precomputing and generally pre-configuring backup paths capable to reroute traffics of affected primary paths upon a failure. To ensure resource availability1

¹
In the rest of this document, resource refers to bandwidth.

after a failure repair, the primary and backup paths should reserve their resources. Whereas the primary paths really use the resources they reserved, the backup paths doesn’t consume any resources before a failure occurrence. Hence, under the single failure assumption, resources can be shared between all the backup paths which protect against different failure risks, since these backup paths cannot be active at the same time. In addition of the resource sharing, the primary paths should follow the shortest paths in order to achieve resource optimization. For instance, the internet routing protocols (RIP [18] and OSPF [21]) are designed to save resource by allowing the computation of shortest paths. Similarly, for virtual netwok embedding k-shortest paths are often chosen to map the virtual links [4,6].

With the arrival of MultiProtocol Label Switching (MPLS) [25] in the few past years, protection [29] and resource optimization [30] are provided efficiently.

Firstly, fast recovery and availability of resources are guaranteed with the pre-configuration of local backup paths capable to bypass any failure risk (a failure risk could be a link, a node or a SRLG2

A SRLG [16,28] corresponds to a set of logical links that share a common physical component (optical fiber, crossconnect, etc.) whose single failure may impact all links in the set.

). Local backup paths ensure fast reaction to failure due to their locality : fast detection and fast rerouting. Two types of backup paths are defined in MPLS for local protection [23]: Next HOP backup Label Switched Path (NHOP LSP3

A LSP is a path through an MPLS network.

) and Next Next HOP backup Label Switched Path (NNHOP LSP). A NHOP LSP (resp. NNHOP LSP) is a backup LSP protecting against link failure (resp. node failure); it is setup between a Label Switched Router (LSR) called Point of Local Repair (PLR) and one LSR called Merge Point (MP). The PLR is the LSR upstream to the failure point. The MP is located between the next-hop (resp. next-next-hop) of the PLR and the destination. The NHOP (resp. NNHOP) backup LSP bypasses the link downstream (resp. the node downstream) to the PLR on the primary LSP. When a link failure (resp. node failure) is detected by an upstream node, this later activates locally all its NHOP and NNHOP (resp. NNHOP) backup LSPs by switching traffic from the affected primary LSPs to their backup LSPs.

Secondly, much resources can be saved thanks to the flexibility in path selection offered by MPLS. Indeed, an appropriate selection of primary and backup paths can increase the bandwidth sharing and thus decrease the bandwidth allocations.

In the last recent years, more attention was given to the virtual networks. For a better use of resources, virtual networks are computed so that they consume less resources. Due to the NP-hardness of the problem of mapping a virtual network to a substrate network (Virtual Network Embedding or VNE), most of the proposed solutions use pre-computed (k-)shortest paths. Like in classical networks, two types of protection could be applied to ensure survivability : global and local. With the global protection, a primary virtual link (which corresponds to a substrate path) is protected by a disjoint backup virtual link connecting the same extremities [24,33]. Two virtual links are said disjoint if they don’t share any link or internal node in the substrat network. With the local protection [9], each link or node belonging to a substrat primary path (i.e. primary virtual link) is protected locally by a backup path which bypasses it.

Two main resources sharing strategies are defined in literature: (1) backup resource sharing [15] and (2) global resource sharing [1]. With the first strategy, the resource sharing is limited and applied to the backup paths protecting against different failure risks. As these backup paths cannot be active at the same time (due to the single failure assumption), they cannot ask for their resources simultaneously and thus they can share them. With the second strategy, the resource sharing is extended and applied to primary and backup paths. Concretely, since a backup path can bypass several links and/or nodes of a primary path, some resources can be freed on the primary affected paths. Such resources can be reallocated to the backup paths.

In this paper, we study the impact of resources sharing strategies on the resource utilization when the primary paths are the shortest ones. After reviewing works related to the resource sharing in Section 2, we introduce and explain in more details the principles of the backup and global resource sharing strategies. Then, we determine in Section 3 the formulas computing the amount of sharable and allocated resources with application to the two sharing strategies. In Section 4, we study formally the impact of resource sharing strategies on the resource utilization when the primary paths are the shortest ones. We show that the impact of the primary path resources freed upon a failure is very low and negligible on the protection capability. In Section 5, we compare and measure by simulations the gain obtained by global resource sharing instead of backup resource sharing. Finally, Section 6 is dedicated to the conclusions.

2. Related works

In the last two decades, a great deal of work is addressing network protection to find efficient algorithms and mechanisms providing survivability and optimizing network resource utilization.

In [12,13], several network coding-based strategies are described to provide protection in optical and also higher layers. In [22], re-optimization heuristic is proposed in order to decrease the risk of link congestion and thus avoid service disruption. With such heuristic, resource allocations are balanced over the network, mainly by rearranging and rerouting the paths. In [5], an extensive survey of the recovery methods is given. These methods are classified according to different criteria such as the layer in which recovery methods are applied (Physical Layer, Link Layer, Network Layer, etc.), computation and/or establishment moment of the backup paths (before failure for protection and after failure occurrence for the restoration), resource usage (without resource sharing or with resource sharing), scope (global or local protection) and domain (intra-domain or inter-domain protection). In MPLS networks, and under different network parameters and constraints, [3,10] propose various comparison metrics, such as the packet loss, rejection probability and restoration time, to evaluate the level of protection. Unfortunately, nether [3,10] nor [5] consider global sharing in their studies.

For MPLS networks, global and local protection with/without resource sharing can be applied in both intra-domain and inter-domain. With the global protection [2,15], two disjoint paths connecting the source and target nodes are computed: one primary path used to transmit traffic before any failure occurrence and one backup path that should be activated and used for routing upon any failure affecting the primary path. With the local protection [1,20,31], for every link and/or node of the primary path, one local backup path (NHOP LSP or NNHOP LSP) bypassing the protected link and/or node is computed. When a failure occurs, the traffic is switched locally at the PLR to the backup paths bypassing the failed risk. In [17], Li et al. proves that joint resource optimization of primary and local backup path is an NP-hard problem.

Recently, several methods were proposed for virtual network survivability [11,19]. Due to the complexity of the survivable virtual network embedding (SVNE) problem, this later is generally subdivided into two sub-problems (VNE and protection) which can be solved separately. Whereas on-line protection is applied to protect one path in classical networks, many substrat paths should be protected together to provide protection. In [33], the authors proposed to protect each primary substrat path by a disjoint shortest substrat path. To save resources, the backup paths minimize the additional bandwidth. In [9], the authors propose to protect locally the substrat links which are used to form the virtual links. In their approach, Guo et al. firstly chose a subset of primary and backup paths before calling a linear procedure that optimizes bandwidth allocation while balancing the load. In [11,19], various approaches providing survivability for virtual networks are described. These approaches are grouped in various categories according to the type of recovery (proactive or reactive), the protected network component (node or link), the recovery procedure (replication or flow rerouting), the scope (centralized or distributed), etc. [8] proposes to combine the failure dependent protection (FDP) with the failure independent protection (FIP) to improve the resource utilization. FDP provides node protection by duplicating nodes (i.e. associating backup nodes to the primary nodes) whereas FIP corresponds to the classical protection which configures a set of backup paths. In [32], disaster failures which involve multiple simultaneous failures located in the same geographic region are treated. After modeling disaster failures, the paper proposed mixed integer linear programming and prediction-based heuristics to deal with such type of failures.

To increase the acceptance rate of protection requests (i.e., to improve the resource utilization), [20] proposes a global resource sharing strategy for on-line protection. Contrarily to the backup resource sharing strategy which limits the resource sharing to the backup paths, Mélon et al. [20] suggest to pre-allocate the resources freed by the deactivated (or bypassed) primary path segments upon a failure to the backup paths which will be activated to recover from that failure (see Section 3). In order to minimize the resource allocation, [1] proposes a resource sharing-based cost function that measures the amount of extra spare resources required to cross a given link. Obviously, larger are the primary resources freed on a link upon a failure, smaller is the cost of this link for that failure. As this link cost function depends only on the capacities of resource sharing, the backup path and thus the recovery time may be arbitrary long. Indeed, the backup paths optimizing the cost function may include very long paths which induce high transmission delays. In addition, optimizing the resource allocation does not systematically improve the acceptance rate because of resource sharing capabilities of backup path computations.

Although the primary paths often correspond to the shortest ones, none of the described works studies the impact of such primary routing decision on the protection rate and bandwidth sharing capabilities. In this paper, we try to fill the gap by extending the work in [26] to empirically measure the impact of an optimal primary routing on the quality of resource allocation. In addition, we provide the theoretical results proving that the improvements due to the freed resource reallocation are insignificant compared to those obtained with the utilization of resource sharing between the backup paths.

3. Bandwidth allocation model

Before the presentation of the link admission control that takes into account bandwidth sharing (Section 3.1) for path computation, we first give some notations and definitions useful to the understanding of our control admission models (Section 3.2). Furthermore, these definitions enable the description of the context of our study.

3.1. Notations

Let us consider a directed graph $G = (V, E, \vec{w}, \vec{C} = \vec{P C} + \vec{R C})$ where V is the set of vertices, E the set of links and $\vec{w}$ , $\vec{P C}$ and $\vec{R C}$ are functions that associate respectively to each link $(λ \in E)$ a strictly positive constant weight $w (λ)$ , a primary bandwidth capacity expressed in bandwidth units $P C^{λ}$ and a finite protection bandwidth capacity $R C^{λ}$ expressed in bandwidth units. We define:

the weight $w (π)$ of a primary path π as follows: $\begin{matrix} w (π) = \sum_{λ \in π} w (λ) . \end{matrix}$

${Pr}_{r}^{(s, t)}$ as the set of primary paths crossing the failure risk r (link, node or a set of links and/or nodes) and interconnecting the source node s to the target node t. All the paths in ${Pr}_{r}^{(s, t)}$ are the shortest ones.

$P^{λ}$ as the primary bandwidth that should be reserved on each link λ to carry out traffic before failures. It is computed as the cumulated bandwidth of primary paths crossing the risk λ and connecting s to t.

${Bp}_{r}^{(s, t)}$ as the set of backup paths protecting the primary paths in the set ${Pr}_{r}^{(s, t)}$ .

$δ_{r}^{λ}$ as the protection cost of risk r on link λ. It corresponds to the cumulated bandwidth of backup paths which will be activated on link λ to cope with the failure of risk r.

$L_{r}^{λ}$ corresponds to the (primary) bandwidth freed on link λ upon failure of risk r.

two bandwidth allocation methods on links: bidirectional and unidirectional. With the first method, any two unidirectional links ( $u \to v$ and $v \to u$ ) which share the same physical conductor $u - v$ use the same pool for bandwidth allocations. With the second bandwidth allocation method, each unidirectional link has its own autonomous pool that it uses for bandwidth allocations.

For the ease of understanding and without loss of generality, we will focus in this paper on the case of unidirectional bandwidth allocations. As the case of bidirectional bandwidth allocations can be treated in the same way, only the results of simulations are given and discussed.

3.2. Bandwidth constraints and allocations for the backup paths

Using local protection mode, regardless of resource sharing strategies, $N - 1$ local backup paths (detours) should be built to protect a path that traverses N nodes. For instance, to fully protect path $p_{1} = D \to C \to F$ in Fig. 1(a), two backup paths $b_{1 C} = D \to G \to F$ and $b_{1 F} = C \to B \to E \to F$ are established. The first backup path interconnects the PLR node D to the merge node F whereas the second backup path connects the PLR node C to the merge node F. Thus, the first backup path is a NNHOP LSP protecting against the failures of PLR’s downstream node (C) and link ( $D - C$ ) whereas the second backup path is a NHOP LSP protecting against the PLR’s downstream link ( $C - F$ ).

Fig. 1.

MPLS protection and bandwidth sharing.

To improve the acceptance rate of path establishment requests, resources like the bandwidth should be saved by sharing them. Indeed, under the practical hypothesis of simple failure that we adopt in this paper (as in many articles [1,7,14]), some paths cannot carry traffic at the same time: they can therefore share their bandwidth allocations. For this purpose, two main bandwidth sharing strategies were defined: (1) backup bandwidth sharing and (2) global bandwidth sharing.

With the first bandwidth sharing strategy, the bandwidth sharing is applied and limited to the backup paths that protect against different failure risks. In Fig. 1(a), the backup path $b_{2 C}$ ( $A \to B \to E \to F \to G$ ) protecting the primary path $p_{2}$ ( $A \to C \to D \to G$ ) against failures of node C and link $A - C$ can share its resource allocation (for instance, on links $B - E$ and $E - F$ ) with the backup path $b_{1 F}$ ( $C \to B \to E \to F$ ) which protects the primary path $p_{1}$ ( $D \to C \to F$ ) against the failure of link $C - F$ . Indeed, paths $b_{2 C}$ and $b_{1 F}$ cannot be active at the same time since they protect against disjoint sets of failure risks (failure of link $A - C$ for $b_{2 C}$ and, link $C - F$ for $b_{1 F}$ ). Thus, after determining the protection cost $δ_{r}^{λ}$ of risk r on link λ which correspond to the cumulative bandwidth of backup paths that should be activated to recover from failure r, we determine the protection bandwidth4

⁴

Protection bandwidth corresponds to the minimum amount of bandwidth that should be reserved for backup paths, to ensure the availability of enough bandwidth after any single failure.

R^{λ}

that should be reserved for protection on the (unidirectional) link λ as follows:

\begin{array}{rcl} (1) & R^{λ} = max_{r} δ_{r}^{λ} \end{array}

The total bandwidth $b w (λ)$ allocated on λ must be always smaller than the capacity $C^{λ}$ of link λ: $\begin{array}{rcl} (2) & b w (λ) = P^{λ} + R^{λ} = P^{λ} + max_{r} δ_{r}^{λ} ⩽ C^{λ} \end{array}$ where $P^{λ}$ is the cumulative bandwidth of the primary paths traversing link λ.

In addition of the bandwidth sharing between the backup paths, more bandwidth could be saved by reallocating the bandwidth freed by the bypassed part of the primary path affected by the failure [1]. For instance, to recover from failure of node C in Fig. 1(a), the traffics of the primary paths $p_{1}$ and $p_{2}$ will be rerouted and switched to the backup paths $b_{1 C}$ and $b_{2 C}$ respectively. As shown in Fig. 1(b), the recovery from the failure of node C frees up bandwidth on some primary links. Typically, when node C fails, the traffic of primary path $p_{2}$ (old $p_{2}$ in Fig. 1(b)) will be switched onto backup path $b_{2 C}$ (repaired path $p_{2}$ in Fig. 1(b)). Thus, some bandwidth will be freed on link $D - G$ after the node failure recovery. In order to save bandwidth, the global bandwidth sharing strategy proposes to reuse the bandwidth freed up5

⁵

Only the primary links located between the extremity nodes of the activated backup path frees up bandwidth.

after the recovery of failure r by reallocating it to the backup paths that protect against the same failure r. In our example of Fig. 1, the bandwidth allocated on link

D - G

can be shared between the primary path

p_{2}

and the backup path

b_{1 C}

(see Fig. 1(a)) since these two paths cannot be active at the same time. Indeed, in the absence of C failure, link

D - G

carries only the traffic of the primary path

p_{2}

. If node C fails, only the traffic of the activated backup path

b_{1 C}

will traverse the link

D - G

since the traffic of the primary path

p_{2}

will be switched to the backup path

b_{2 C}

that does not traverse

D - G

\begin{array}{rcl} (3) & R^{λ} = max_{r} (δ_{r}^{λ} - L_{r}^{λ}, 0) \end{array}

We deduce the total amount of bandwidth $b w (λ)$ allocated on the link λ as follows: $\begin{array}{rcl} (4) & b w (λ) = P^{λ} + R^{λ} = P^{λ} + max_{r} (δ_{r}^{λ} - L_{r}^{λ}, 0) ⩽ C^{λ} \end{array}$

Note that all the parameters ( $P^{λ}$ , $δ_{r}^{λ}$ and $L_{r}^{λ}$ ) that are necessary to verify the admission control (i.e. ensure the availability of enough bandwidth before and after any failure) are known by the extremity nodes of link λ since these two nodes know all the paths that traverse them.

Furthermore, to control and specify the amount of resources that should be used for protection and to separate the computation task of primary paths from that of backup paths, the bandwidth capacity of each link λ can be divided in two separate pools: primary bandwidth pool $P C^{λ}$ and protection bandwidth pool $R C^{λ}$ . The primary bandwidth pool is used to allocate bandwidth for primary paths whereas the protection bandwidth pool is used to allocate bandwidth for backup paths. With such bandwidth allocation model, link λ can be included in the computation of a new backup path iff the resulted protection bandwidth on link λ remains lower or equal to the protection capacity.

When the backup resource sharing strategy is applied: $\begin{array}{rcl} (5) & R^{λ} = max_{r} δ_{r}^{λ} ⩽ R C^{λ} \end{array}$ When of global resource sharing strategy is applied: $\begin{array}{rcl} (6) & R^{λ} = max_{r} (δ_{r}^{λ} - L_{r}^{λ}, 0) ⩽ R C^{λ} \end{array}$

Although it seems that the global resource sharing strategy is more efficient than the backup resource sharing strategy, the blocking probabilities6

⁶

The blocking probability corresponds to the probability that a request of path establishment will be rejected due to the lack of network resources (bandwidth).

of the two strategies could be very close, especially when the primary paths correspond to the shortest ones in terms of a static7

⁷

We recall that a metric is said to be static if its values on links do not change.

metric. In the two following sections, we prove formally and by simulations that both the two strategies of resource sharing have close blocking probabilities.

4. After-effect of the amount of freed bandwidth on the backup path acceptance

The majority of the well known IGP protocols computes the primary paths as the shortest ones in terms of a static metric (i.e., traffic independent costs). For instance, RIP minimizes the hop number (number of intermediate routers in a path) while OSPF applies the SPF (shortest path first) algorithm to optimize a static metric that depends generally on bandwidth capacities of links. With the advent of MPLS, the IP routing protocols (OSPF-TE and ISIS-TE) are extended to take into account the traffic characteristics in route computations. This leads to the definition of new (semi-)dynamic metric-based routing algorithms which often applies the Dijkstra’s shortest path algorithm. For instance, CSPF (constrained shortest path first) prunes links that do not meet the configured constraints from the topology network before applying the SPF algorithm that derives the best available path based on the information in the traffic engineering database. In other words, CSPF always returns a shortest path while the pruned links don’t cut all the possible shortest paths between two nodes.

In addition of the IGP protocols, we note that for VNE the k-shortest paths are often selected to map the virtual links to the primary substrat paths (i.e. primary virtual links).

Fig. 2.

Links that are able to free up bandwidth upon a failure of link $D - G$ .

In this section, we show that when the primary paths follow the shortest paths according to any static metric, the maximum number of backup paths is bounded even if the primary bandwidth freed upon failure is infinite (i.e., the freed bandwidth is very larger than the protection bandwidth). This means that any backup path must cross at least one link which cannot free up bandwidth upon failure of the protected risk (i.e. we cannot build a backup path with only links freeing bandwidth upon the failure of the protected risk). Hence, the maximum number of backup paths which can be built is bounded at least by the capacities of links which cannot free up bandwidth (upon the considered failure).

Before detailing the proof of our assertion, let us consider an example. In Fig. 2, a network topology of equal-cost links is depicted. Assume that any primary path follows a shortest path and requires a minimum of 1 bandwidth unit. To protect a primary path traversing node D, link $D - G$ then node G (in this order), it is sufficient to determine a backup path that connects the PLR D to node G or any node downstream to G (on the shortest primary path). As the primary paths should follow the shortest paths (dashed arrows in Fig. 2), only nodes F and G can be located on the downstream of G. In addition, the shortest primary paths traversing node D, link $D - G$ and node G (in this order) can only free up bandwidth on links $G - F$ and $G - H$ located on the downstream of the failed link $D - G$ . In a same way, we deduce that any backup path protecting a primary path traversing node G, link $G - D$ and node D (in this order) should connect the PLR G to node D or any node downstream to D on a shortest path (i.e. any node in {A, B, C, E}). The links that are able to free up bandwidth on a primary path traversing node G, link $G - D$ and node D (in this order), upon a failure of link $G - D$ are: $D - C$ , $C - A$ , $D - B$ , $B - A$ , $B - E$ (in the two directions) and $D - E$ (links associated to bold arrows in Fig. 2).

From the precedent remarks, we conclude that any backup path protecting link $D - G$ should use link $H - E$ or link $F - C$ . Since these two last links will not free up bandwidth after the failure of link $G - D$ , we deduce that the number of backup paths protecting link $G - D$ is bounded by the capacities of links $H - E$ and $F - C$ (the protection costs $δ_{G - D}^{H - E}$ and $δ_{G - D}^{F - C}$ increase with the establishment of backup paths protecting against the failure of link $G - D$ ).

Even if we consider that the freed bandwidth upon failure r is infinite on all the links that are capable to free up bandwidth (example: when the primary capacities are infinite whereas the protection capacities are finite), we show formally in the next paragraphs that the maximum number of backup paths is bounded. Without loss of generality, we assume that any backup path requires a minimum of 1 bandwidth unit and the protection bandwidth is bounded.

Lemma 4.1.

Any backup path protecting a primary shortest path (according to a static metric) against a link failure risk must include a link which doesn’t free up any bandwidth. Formally: $\begin{matrix} \forall r \in E, \forall π \in {Bp}_{r}^{(s, t)}, \exists λ \in π : L_{r}^{λ} = 0 \end{matrix}$

Proof.

To free up bandwidth on a link λ upon failure of link $plr - p_{1}$ ,8

⁸

Even if we consider that the PLR $plr$ is not adjacent the failed link $p_{f} - p_{i}$ (case of the global protection), we can easily prove the correctness of Lemma 4.1. Indeed, if Lemma 4.1 is valid for any backup path $p_{f} \to \dots \to p_{j_{j ⩾ i}}$ protecting against the failure risk $p_{f} - p_{i}$ , it implies that it is valid for any backup path $p_{f} \to \dots \to plr \to \dots \to p_{j_{j ⩾ i}}$ protecting against the failure risk $p_{f} - p_{i}$ . As all the links of the sub-path $p_{f} \to \dots \to plr$ can free up bandwidth upon a failure of link $p_{f} - p_{i}$ , we conclude that Lemma 4.1 is valid for any backup path $plr \to \dots \to p_{j_{j ⩾ i}}$ protecting against the failure risk $p_{f} - p_{i}$ .

λ must belong to at least one shortest primary path traversing link

plr - p_{1}

in one direction (from

plr

p_{1}

or from

p_{1}

plr

). In addition, link λ must be located on the downstream of link

plr - p_{1}

Let us define ${Down}_{(plr, p_{1})}$ as a set of nodes located downstream to $plr \to p_{1}$ (in this direction) on the primary paths traversing $plr$ and $p_{1}$ (see Fig. 3). Here we prove that ${Down}_{(plr, p_{1})} \cap {Down}_{(p_{1}, plr)} = \emptyset$ .

Assume that there is a node $b_{i}$ so that $b_{i} \in {Down}_{(plr, p_{1})}$ . This means that: $\begin{array}{rcl} (7) & \begin{matrix} w (plr, b_{i}) < w (p_{1}, b_{i}) \end{matrix} \end{array}$ Where $w (plr, b_{i})$ is the weight of any shortest path connecting node $plr$ to node $b_{i}$ and $w (plr, b_{i})$ is the weight of any shortest path connecting node $p_{1}$ to node $b_{i}$ .

Actually, assume that $b_{i} \in {Down}_{(p_{1}, plr)}$ . This means that: $\begin{array}{rcl} (8) & \begin{matrix} w (p_{1}, b_{i}) < w (plr, b_{i}) \end{matrix} \end{array}$

From formulas (7) and (8), we conclude that $b_{i} \in {Down}_{(plr, p_{1})} \cap {Down}_{(p_{1}, plr)}$ leads to the following contradiction: $w (plr, b_{i}) < w (p_{1}, b_{i}) < w (plr, b_{i})$ . As a result, we deduce that: $\begin{matrix} {Down}_{(plr, p_{1})} \cap {Down}_{(p_{1}, plr)} = \emptyset \end{matrix}$

Fig. 3.

Links forming primary and backup paths.

As the PLR node belongs to ${Down}_{(p_{1}, plr)}$ whereas the merge node is in ${Down}_{(plr, p_{1})}$ , no backup path connecting the PLR to the merge point could be established. Indeed, any link connecting a node in ${Down}_{(p_{1}, plr)}$ to a node in ${Down}_{(plr, p_{1})}$ cannot free up bandwidth (by definition, the extremity nodes of a link freeing bandwidth are in the same set ${Down}_{(plr, p_{1})}$ or ${Down}_{(p_{1}, plr)}$ ). □

Lemma 4.2.

Any backup path protecting a primary shortest path (according to a static metric) against a node failure risk must include a link which doesn’t free up any bandwidth. Formally: $\forall r \in V, \forall π \in {Bp}_{r}^{(s, t)}, \exists λ \in π : L_{r}^{λ} = 0$

Proof.

We prove the validity of lemma 4.2 by contradiction. In other words, if such a backup path exists, it must be shorter than the primary path it protects.

Assume that there is one backup path $b = plr \to b_{1} \to \dots \to b_{j}$ (see Fig. 3) composed of only links freeing up bandwidth after the failure of node $p_{1}$ (downstream to the PLR node $plr$ ). The backup path b protects a primary shortest sub-path $p = plr \to p_{1} \to \dots \to p_{i} \to b_{j}$ according to the static metric $\vec{w}$ (see Fig. 3). Let us prove by induction on the kth backup nodes that: $\begin{array}{rcl} (9) & \forall k ⩽ j, \exists s \in {Paths}^{(plr, b_{k})}, \forall π \in {Paths}^{(p_{1}, b_{k})} : w (π) ⩾ w (p_{1} ↷ plr \to s \to b_{k}) \end{array}$ where $p_{1} ↷ plr$ is any shortest path from $p_{1}$ to $plr$ .

$k = 1$

To free up bandwidth upon failure of node $p_{1}$ (see Fig. 3), link $plr \to b_{1}$ must belong to at least one shortest primary path traversing node $p_{1}$ . In addition, link $plr \to b_{1}$ must be located on the downstream of node $p_{1}$ . This implies that: $\exists s = plr \to b_{1} \in {Paths}^{(plr, b_{1})}$ so that: $\begin{matrix} p_{1} ↷ plr \to s \to b_{1} is a shortest path \end{matrix}$ This means that formula (9) is valid for $k = 1$ .

Step $1 < k ⩽ j$

Assume that formula (9) is valid for $n = \overline{1, k - 1}$ and prove that it is valid for $n = k$ . To free up bandwidth upon failure of node $p_{1}$ , link $b_{k - 1} \to b_{k}$ must belong to at least one shortest primary path traversing node $p_{1}$ . In addition, link $b_{k - 1} \to b_{k}$ must be located on the downstream of node $p_{1}$ . This implies that: $\begin{matrix} \exists s \in {Paths}^{(p_{1}, b_{k - 1})}, \forall π \in {Paths}^{(p_{1}, b_{k})} : w (π) ⩾ w (p_{1} \to s \to b_{k - 1} \to b_{k}) \end{matrix}$ As for $n = k - 1$ , we have: $\begin{matrix} \exists s^{'} \in {Paths}^{(plr, b_{k - 1})}, \forall π^{'} \in {Paths}^{(p_{1}, b_{k - 1})} : w (π^{'}) ⩾ w (p_{1} ↷ plr \to s^{'} \to b_{k - 1}), \end{matrix}$ we deduce that $\begin{array}{rcl} (for π^{'} = p_{1} \to s \to b_{k - 1}) : \\ w (π) ⩾ w (p_{1} \to s \to b_{k - 1} \to b_{k}) = w (p_{1} \to s \to b_{k - 1}) + w (b_{k - 1} \to b_{k}) \\ ⩾ w (p_{1} ↷ plr \to s^{'} \to b_{k - 1}) + w (b_{k - 1} \to b_{k}) = w (p_{1} ↷ plr \to s^{'} \to b_{k - 1} \to b_{k}) \end{array}$

Thus, path $p_{1} ↷ plr \to s^{″} \to b_{k}$ (with $s^{″} = s^{'} \to b_{k - 1}$ and $s^{″} \in {Paths}^{(plr, b_{k})}$ ) is also a shortest path according to the metric $\vec{w}$ . In other words, formula (9) is verified.

To prove the correctness of Lemma 4.2, we show now that formula (9) contradicts the shortness of the primary path $plr \to p_{1} \to p_{i} \to b_{j}$ .

We recall that the primary path $plr \to p_{1} \to \dots \to p_{i} \to b_{j}$ corresponds to a shortest path. This implies that: $\forall π \in {Paths}^{(p_{1}, b_{j})} : w (π) ⩾ w (plr \to p_{1} \to \dots \to p_{i} \to b_{j})$ . Thus, for any segment path $s \in {Paths}^{(plr, b_{j})}$ , we have: $w (plr \to s \to b_{j}) ⩾ w (plr \to p_{1} \to \dots \to p_{i} \to b_{j})$ .

On the other hand, formula (9) implies for $k = j$ that: $\exists s^{'} \in {Paths}^{(plr, b_{j})} \forall π^{'} \in {Paths}^{(p_{1}, b_{j})} : w (π^{'}) ⩾ w (p_{1} ↷ plr \to s^{'} \to b_{j}) = w (p_{1} ↷ plr) + w (plr \to s^{'} \to b_{j}) ⩾ w (p_{1} ↷ plr) + w (plr \to p_{1} \to \dots \to p_{i} \to b_{j}) = w (p_{1} ↷ plr \to p_{1}) + w (p_{1} \to \dots \to p_{i} \to b_{j}) > w (p_{1} \to \dots \to p_{i} \to b_{j})$ . This leads to a contradiction since for $π^{'} = p_{1} \to \dots \to p_{i} \to b_{j}$ ( $π^{'} \in {Paths}^{(p_{1}, b_{j})}$ ), we obtain: $w (π^{'}) = w (p_{1} \to \dots \to p_{i} \to b_{j}) > w (p_{1} \to \dots \to p_{i} \to b_{j})$ . Thus, formula (9) cannot be verified. In other words, any backup path protecting against a node failure risk must utilize at least one link which cannot free up bandwidth upon that node failure. □

Proposition 4.3.

Every backup path (NNHOP LSP or NHOP LSP) should traverse a link that cannot free up bandwidth after the failure of a protected risk.

Proof.

As both the NHOP and NNHOP paths should protect against link failures,9

⁹

This is due to the difficulty to distinguish link and node failures.

we conclude from Lemma 4.1 that every backup path should traverse a link that don’t free up bandwidth after a failure of a protected link. □

Theorem 4.4.

The number of NHOP and NNHOP backup paths that can be build in a network $G = (V, E, \vec{w}, \vec{P C}, \vec{R C})$ is bounded if $| E |$ and ${(R C^{λ})}_{\forall λ \in E}$ are bounded (by constants).

Proof.

For the proof, we first show that for any link, the number of backup paths protecting against its failure is bounded. From Lemma 4.1, we know that any backup path protecting against any link failure risk $r_{l}$ should traverse at least one link λ that cannot free up bandwidth after the failure $r_{l}$ . From formula (6), we have: $\begin{matrix} δ_{r_{l}}^{λ} - L_{r_{l}}^{λ} = δ_{r_{l}}^{λ} ⩽ R^{λ} ⩽ R C^{λ} \end{matrix}$

As the protection cost $δ_{r_{l}}^{λ}$ corresponds to the number of (1 bandwidth unit) backup paths protecting against the failure $r_{l}$ and traversing link λ, we deduce that this number of backup paths is bounded by $R C^{λ}$ . Because the number of links freeing up some bandwidth after the failure of $r_{l}$ is lower than $| E |$ (it is always equal to 0 if we apply the backup bandwidth sharing strategy), we conclude that the number of backup paths protecting against the link failure risk $r_{l}$ is bounded by $\sum_{λ \in E} R C^{λ} ⩽ | E | \times {max}_{λ \in E} (R C^{λ})$ .

Similarly, we deduce that the maximum number of backup paths that can be built in the network is bounded by $| E |^{2} \times {max}_{λ \in E} (R C^{λ})$ since the number of distinct link failure risks is lower or equal to $| E |$ . □

Interpretation:

With both the global and backup bandwidth sharing strategies, the number of backup paths is bounded when the protection capacities (or the link capacities) are bounded and lower than given constants. As any backup path should traverse at least one link that don’t free up bandwidth, the use of the global bandwidth sharing strategy instead of the backup bandwidth sharing strategy could not avoid network redimensioning over the long term.

When a great amount of traffic is not protected (for instance, best-effort traffic does not require protection), the freed bandwidth on some links upon failure could be high. Even in this case, the maximum number of backup paths is bounded specifically by the capacity of links that cannot free up bandwidth.

Whereas the maximum number of backup paths depends on all the network links with the backup bandwidth sharing strategy, this number depends more on the links that cannot free up bandwidth with the global bandwidth sharing strategy. In the next section, we compare by simulations these two bandwidth sharing strategies to quantify the gain in performances due to the exploitation of the freed bandwidth.

5. Performance evaluation

5.1. Simulation model

To compare and measure the performances of global and backup bandwidth sharing strategies, we used two well known topologies of network: Long Haul and Cost 239. The first network topology, depicted in Fig. 4(a), is composed of 28 nodes and 45 bidirectional links. The protection capacities are equal to 600 units in each direction for the bold links and 200 units for the light links. This network topology is relatively wide and presents a mean connectivity degree of 3.21. The second network topology, depicted in Fig. 4(b), is composed of 11 nodes and 26 bidirectional links. It is small and strongly connected since its mean connectivity degree is equal to 4.73. All the links of this network have the same protection capacity that is equal to 200 units in each direction.

To take into account the two possible models of bandwidth allocation (unidirectional bandwidth allocation and bidirectional bandwidth allocation), we considered two test scenarios: unidirectional allocation-based scenario (UAS) and bidirectional allocation-based scenario (BAS). In the first test scenario, the unidirectional bandwidth allocation method is applied for bandwidth allocation. It means that two protection pools are associated to each bidirectional link in Fig. 4. In the second test scenario, the bidirectional bandwidth allocation method is applied for bandwidth allocation. It means that only one protection pool is associated to each bidirectional link in Fig. 4. Thus, the protection capacities of bold links are equal to 1200 units ( $600 \times 2$ ) whereas they are equal to 400 units ( $200 \times 2$ ) on the light links.

Fig. 4.

Network topologies.

In our simulations, we generated sequentially 1000 demands of primary path protection asking for bandwidth quantities uniformly distributed between 1 and 10 units. Each demand corresponds to one primary path establishment request that is always satisfied (i.e., we assumed that the primary pool capacities of links are sufficient to satisfy all the requests of primary path establishment) and several requests of backup path establishment allowing the protection of the built primary path. The source and target nodes of each primary path are selected uniformly among the set of network nodes. For the computation of primary paths, we applied the shortest path first (SPF) algorithm that optimizes the number of hops whereas we used the constrained shortest path first (CSPF) algorithm for the computation of backup paths. With the backup resource sharing strategy, a request of backup path establishment is satisfied iff equation (5) is verified. With the global resource sharing strategy, equation (6) must be verified to establish the requested backup path.

Two criteria are selected to compare the global and backup resource sharing strategies: acceptance rate of backup paths (BPA) and rate of protection bandwidth utilization (PBwU). The first criterion BPA is computed for different network loads. It corresponds to the instantaneous ratio between the number of backup path requests that are accepted and the total number of backup paths required to protect entirely the last 50 primary paths. Formally, it is determined as follows: $\begin{matrix} BPR = \frac{# accepted protection requests}{# protection requests} \end{matrix}$ Note that a backup path is accepted if and only if there are enough resources.

The second criterion PBwU determines and measures the efficiency of bandwidth sharing. It corresponds to the ratio between the sum of all the protection costs and the amount of the bandwidth allocated in the network for the protection. Formally, it is computed as follows: $\begin{matrix} PBwU = \sum_{(λ, r) \in E \times (V \cup E)} δ_{r}^{λ} / \sum_{λ \in E} R^{λ} . \end{matrix}$

For each test scenario (UAS and BAS) and at each establishment of 50 primary paths, the two metrics BPR and PBwU are computed for the two compared strategies. We note that our results correspond to mean values over 1000 experiments.

5.2. Results and analysis

Figure 5 depicts the evolution of the instantaneous acceptance rate of backup paths (BPA) as a function of the number of primary paths setup in the network for the unidirectional and bidirectional bandwidth allocations. We recall that an instantaneous acceptance rate concerns the 50 last primary paths only. Figure 5 shows that the bidirectional bandwidth allocation method is slightly better that the unidirectional bandwidth allocation method.

Fig. 5.

Evolution of the mean rate of backup path acceptance.

Fig. 6.

Evolution of the difference in acceptance rates of backup paths.

In addition, Fig. 5 clearly shows that the global and backup bandwidth sharing strategies using the bidirectional bandwidth allocation method have respectively larger acceptance rates than the global and backup bandwidth sharing strategies using the unidirectional bandwidth allocation method. These observations can be explained by the distribution of the protection costs on links (especially on opposite links) which is heterogeneous [27].

Figure 6 depicts the difference in cumulated acceptance rates of backup paths for the unidirectional and bidirectional bandwidth allocations. It shows that the difference is small and even imperceptible sometimes. For instance, in Longhaul network topology, the difference in instantaneous acceptance rates does not exceed 8%, even for high loads of traffic (a large number of primary paths) where the instantaneous acceptance rate of backup paths is small and inefficient (see Fig. 5(a)). For usual instantaneous acceptance rates that should be larger than 90%, the difference between the compared strategies is often imperceptible. With regards to the cumulated acceptance rate, Fig. 6(a) shows that the difference is very low and smaller than 3% in Longhaul network topology. In Cost 239 network topology, the differences in instantaneous acceptance rates reaches 30% (see Fig. 5(b)) for high loads whereas it does not exceed 9% for the cumulated rates (see Fig. 5(b)).

Obviously, the difference in the acceptance rates of backup paths is directly related to the amount and distribution of the freed bandwidth on links. Since the freed bandwidth is statically high on the links close to PLRs and generally low on the links located far from PLRs, the difference in acceptance rates of the compared strategies is slightly higher in COST 239 network topology than in Longhaul network topology. Indeed, the links are closer to the PLRs in COST 239 since it is more homogeneous and it has a larger connectivity degree than Longhaul.

In addition of the previous observations, we note that even for high freed bandwidth values, the acceptance rates of backup paths decrease with the augmentation of the traffic load and they converge to the saturation state where almost all the new protection requests are rejected. This corroborates our theoretical results which announces the existence of an upper bound for the number of backup paths that can be established in the network even with unlimited resources.

With regards to the second metric (bandwidth sharing utilization), Fig. 7 shows that both the global and backup bandwidth sharing strategies have similar bandwidth utilization rates for small and usual acceptance rates of backup paths. For instance, the difference in bandwidth sharing utilization for the compared strategies is very small in Longhaul network (see Fig. 7(a)) when the number of primary paths is lower than 1000 (all the acceptance rates are larger than 0.7) whereas the difference is imperceptible in COST 239 network (see Fig. 7(b)) when the number of primary paths is lower than 3000 (all the acceptance rates are larger than the usual value 0.85). For high traffic loads, Fig. 7 shows that the global bandwidth sharing strategy is better than the backup bandwidth sharing strategy. This is essentially due to the amount of freed bandwidth which increases with the decrease of the acceptance rate of backup paths. Indeed, whereas the protection bandwidth is completely independent of the freed bandwidth variation when the backup bandwidth sharing strategy is applied, it decreases with the augmentation of the freed bandwidth when we apply the global bandwidth sharing strategy.

Fig. 7.

Evolution of the mean rate of protection bandwidth utilization.

To summarize, these simulations show that the difference in performances between the global and backup bandwidth sharing strategies is almost imperceptible for low traffic loads where the acceptance rate of backup paths is high and usual. For high traffic loads where the acceptance rate of backup paths is low, the global bandwidth sharing strategy is slightly better than the backup bandwidth sharing strategy. In addition to the precedent remarks, our simulations comfort our theoretical results (see Therem 4.4) and show clearly that the freed primary bandwidth has very slight effect on the acceptance rate of backup paths compared to the backup bandwidth sharing.

6. Conclusion

Two known strategies of resource (bandwidth) sharing are described in this paper: backup bandwidth sharing and global bandwidth sharing. The first strategy restricts the bandwidth sharing to the backup paths whereas the second strategy extends the bandwidth sharing to the primary and backup paths.

To quantify the gain due to the extension of the bandwidth sharing to the primary and backup paths, we firstly proved theoretically that the bandwidth sharing between the primary and backup paths can never be applied on some backup links when the primary paths correspond to the shortest ones according to a static metric. Thus, the acceptance rate of backup paths is always limited and bounded by the protection capacities of links. Secondly, to measure the enhancement due to the bandwidth sharing between the primary and backup paths, we showed by simulations that the gain in performances (acceptance rate of backup paths and bandwidth utilization) is often imperceptible, particularly for low traffic loads where the acceptance rate of backup paths is large and usual. For high traffic loads where the acceptance rates are small, the global bandwidth sharing strategy outperforms slightly the backup bandwidth sharing strategy, especially in strongly connected networks.

As a result, the global bandwidth sharing strategy cannot be a long term solution for supporting bandwidth-intensive applications especially since the global bandwidth sharing strategy induces an overcost. Indeed, in return of the slight performance improvements the global bandwidth sharing allows, we note the complication of path computation and the necessity to maintain larger information. For instance, additional computations should be done with the global bandwidth sharing strategy to determine the amount of freed bandwidth after each establishment or liberation of a primary path.

References

Balon,

Mélon and

Leduc, A Scalable and Decentralized Fast–Rerouting Scheme with Efficient Bandwidth Sharing, Computer Networks 50 (2006), 3043–3063. doi:10.1016/j.comnet.2005.12.002.

Bhandari, Survivable Networks: Algorithms for Diverse Routing, Kluwer Academic Publishers, 1999.

Calle,

J.L.

Marzo and

Urra, Protection performance components in MPLS networks, Computer Communications 27(9) (2004), 1220–1228. doi:10.1016/j.comcom.2004.02.025.

Cheng,

Su,

Zhang,

Wang,

Yang,

Luo and

Wang, Virtual Network Embedding Through Topology-Aware Node Ranking, SIGCOMM Comput. Commun. Rev. 41 (2011), 38–47. doi:10.1145/1971162.1971168.

Cholda,

Mykkeltveit,

B.E.

Helvik,

Wittner and

Jajszczyk, A survey of resilience differentiation frameworks in communication networks, IEEE Communications Surveys and Tutorials 9(1–4) (2007), 32–55. doi:10.1109/COMST.2007.4444749.

Gang,

Zhenmin,

Zhaoming,

Yi and

Xiangming, A Virtual Network Embedding Algorithm based on Mapping Tree, in: 13th International Symposium on Communications and Information Technologies (ISCIT), 2013.

Grover and

Stamatelakis, Cycle-Oriented Distributed Preconfiguration: Ring-like Speed with Mesh-like Capacity for Self-planning Network Restoration, in: Proc. International Conference on Communications, 1998.

Guo,

Qiao,

Wang,

Yu,

Zuo,

Li,

Chen and

He, Survivable virtual network design and embedding to survive a facility node failure, Journal of Lightwave Technology 32(3) (2014), 483–493. doi:10.1109/JLT.2013.2293193.

Guo,

Wang,

Moessner and

Tafazolli, Shared backup network provision for virtual network embedding, in: IEEE International Conference on Communications (ICC), 2011, pp. 1–5.

10.

M.Y.

Hariyawan, Comparison Analysis of Recovery Mechanism at MPLS Network, International Journal of Electrical and Computer Engineering (IJECE) 1(2) (2011), 151–160. doi:10.11591/ijece.v1i2.84.

11.

Herker,

Khan and

An, Survey on Survivable Virtual Network Embedding Problem and Solutions, in: The 9th International Conference on Networking and Services (ICNS), 2013, pp. 99–104.

12.

A.E.

Kamal,

1 + n

Network Protection for Mesh Networks: Network coding-based protection using p-cycles, IEEE/ACM Transactions on Networking 18(1) (2010), 67–80. doi:10.1109/TNET.2009.2020503.

13.

A.E.

Kamal and

Mohandespour, Network Coding-based Protection, Optical Switching and Networking 11(B) (2014), 189–201. doi:10.1016/j.osn.2013.06.006.

14.

Kini,

Kodialam,

T.V.

Lakshman,

Sengupta and

Villamizar, Shared Backup Label Switched Path Restoration, 2001, Internet Draft draft-kini-restoration-shared-backup-01.txt.

15.

M.S.

Kodialam and

T.V.

Lakshman, Dynamic Routing of Restorable Bandwidth–Guaranteed Tunnels using Aggregated Network Resource Usage Information, IEEE/ACM Transactions On Networking 11 (2003), 399–410. doi:10.1109/TNET.2003.813044.

16.

Kompella and

Rekhter, Routing Extensions in Support of Generalized Multi-Protocol Label Switching (GMPLS), RFC 4202 (2005).

17.

Li,

M.M.

Buddhikot,

Chekuri and

Guo, Routing bandwidth guaranteed paths with local restoration in label switched networks, in: 10th IEEE International Conference on Network Protocols (ICNP’02), 2002, p. 110.

18.

Malkin, RIP Version 2, 1998, RFC 2453.

19.

C.C.

Meixner,

Develder,

Tornatore and

Mukherjee, A survey on resiliency techniques in cloud computing infrastructures and applications, IEEE Communications Surveys and Tutorials 18(3) (2016), 2244–2281. doi:10.1109/COMST.2016.2531104.

20.

Mélon,

Blanchy and

Leduc, Decentralized local backup LSP calculation with efficient bandwidth sharing, in: Proceedings of 10th International Conference on Telecommunications (ICT’2003), 2003.

21.

Moy, OSPF Version 2, 1998, RFC 2328.

22.

Palmieria,

Fioreb,

Ricciardic and

Castiglioned, GRASP-based Resource Re-optimization for Effective Big Data Access in Federated Clouds, Future Generation Computer Systems 54 (2016), 168–179. doi:10.1016/j.future.2015.01.017.

23.

Pan,

Swallow and

Atlas, Fast Reroute Extensions to RSVP-TE for LSP Tunnels, 2005, RFC 4090.

24.

M.R.

Rahman and

Boutaba, SVNE: Survivable virtual network embedding algorithms for network virtualization, IEEE Transactions on Network and Service Management 10(2) (2013), 105–118. doi:10.1109/TNSM.2013.013013.110202.

25.

Rosen,

Viswanathan and

Callon, Multiprotocol Label Switching Architecture, RFC 3031 (2001).

26.

M.Y.

Saidi and

Cousin, Resource saving: Which resource sharing strategy to protect primary shortest paths? in: 13th IEEE Annual Consumer Communications & Networking Conference, CCNC January 9-12, 2016, Las Vegas, NV, USA, pp. 297–298, 2016.

27.

M.Y.

Saidi,

Cousin and

J.L.

Le, Roux, “PLR-based heuristic for backup path computation in MPLS networks,”, Computer Networks 53 (2009), 1467–1479. doi:10.1016/j.comnet.2009.01.009.

28.

M.Y.

Saidi,

Cousin and

J.L.

Le Roux, Using shared risk link groups to enhance backup path computation, Computer Networks 53 (2009), 1341–1353. doi:10.1016/j.comnet.2009.01.001.

29.

Sharma and

Hellstrand, Framework for Multi-Protocol Label Switching (MPLS)-based Recovery, 2003, RFC 3469.

30.

J.P.

Vasseur,

Charny,

Le Faucheur,

Achirica and

J.L.

Le Roux, Framework for PCE-based MPLS-TE Fast Reroute Backup Path Computation, 2004, Internet Draft draft-leroux-pce-backup-comp-frwk-00.txt, IETF.

31.

J.P.

Vasseur,

Pickavet and

Demeester, Network Recovery: Protection and Restoration of Optical, SONET-SDH, IP, and MPLS, Morgan Kaufmann Publishers, 2004.

32.

Wang,

Liu,

Qiu and

Li, Prediction-based survivable virtual network mapping against disaster failures, International Journal of Network Management 26 (2016), 336–354. doi:10.1002/nem.1939.

33.

Yu,

Anand and

Qiao, Virtual Infrastructure Design for Surviving Physical Link Failures, The Computure Journal 55(8) (2012), 965–978. doi:10.1093/comjnl/bxs043.

Resource sharing strategies: Which sharing to better protect primary shortest paths?

Abstract

Keywords

1. Introduction

1 In the rest of this document, resource refers to bandwidth.

3. Bandwidth allocation model

3.1. Notations

3.2. Bandwidth constraints and allocations for the backup paths

5.1. Simulation model

References

¹
In the rest of this document, resource refers to bandwidth.