A Novel End-to-End Protection Scheme in Multi-Domain

By Jon Powell,2014-09-09 11:26
18 views 0
A Novel End-to-End Protection Scheme in Multi-Domain


    A Novel End-to-End Protection Scheme in Multi-Domain


    LIANG Kaile, WANG Hongxiang

    5 (School of Infornation and Telecommunication Engineering, Beijing University of Posts and

    Telecommunications, Beijing 100876)

    Abstract: Considering the essential improtance of information technology in today's society, network survivability has been a major concern. While pre-provisoned protection strategies for single-link failure has been well studied in single domain networks, and efforts have been made to mitigate these shcemes to Multi-Domain networks, there are still many challenging problems. Diverse path pair 10

    computation and setup across domains is very complex and challenging due to the limited state information between domains. In this paper, a novel end-to-end diverse path pairs protection heuristic for Multi-Domain networks considering traffic engineering is proposed. It gives significantly lower routing overhead and complexitty. Integer Linear Programming(ILP) formulation aimming to minimize

    15 blocking rate in bandwidth routing optical network is proposed. Meanwhile, the proposed heuristic is evaluated using simulation and compared with both ILP solution and other shceme.

    Keywords: diverse lightpath pairs; protection; multi-domain networks; ILP

    0 Introduction

    20 Compared to post-fault restoration, pre-provision protection strategies have much shorter recovery time and single-failure resiliency guarantees. So it is more suitable for high survivability requirement. Differently categories of pre-provision strategies have been studies. The solutions can be classified into two categories according to the domain diversity, per-domain and

    [1][2] end-to-end. Per-domain protectionfollows the same domain sequence as the primary path to

    25 setup the backup routes. Analysis and simulations show that this strategy has lower resource consumption, but the recovery times are longer and single failure recovery is not guaranteed. Also, at the inter-domain level, this approach requires sufficient link diversity between domains, e.g., dual/multi-homing setups. These restrictions can compromise efficiency greatly in reality and be vulnerable to multiple failures. Also, it is difficult to address inter-domain traffic engineering

    30 concern, e.g., load-balancing. Due to all these constraints, end-to-end protections has been studied to improve the resilience and traffic engineering by using different domain sequences for primary and backup paths.

    Solutions of end-to-end protection are based on partial global state visibility and adopt

    hierarchical distributed path computation. Firstly, a loose route (LR) pair is computed over high

    35 level inter-domain topology, which is obtained by topology abstraction. Then these LRs are expanded along the domains using distributed signaling. IETF path computation element (PCE) and RSVP-TE standards can be used to implement these solutions. However, current end-to-end

    [3][4][5]protection schemes introduce significant computational and routing overhead, which can be

    a main obstacle for real world implementation and usage. Among all these end-to-end protection

    40 efforts, [3] proposed a solution emphasis on link-disjoint paths, which claims to be optimal

    solution. However, the overhead for this scheme is very high, since it requires sufficient global state information to compute the link-disjoint path. Actually the overhead of proposed method to

    4abstract these global information is very high, O(N) for N border nodes in a domain. Also, the

    claimed optimal relay on 0 link-state update time, which cannot happen in real case. Since the

    45 abstraction reveals more information about the intra-domain, privacy concerns may also be an obstacle of implementing in reality.

Brief author introduction:LIANG Kaile, (1987-), Female.

    Correspondance author: WANG Hongxiang, Male, Associate Professor. E-mail:

    - 1 -


    In the light above, this paper proposes an end-to-end protection heuristics to implement path protection. Suurbales algorithm is introduced into the inter-domain loose route (LR) computation stage. Followed by intra-domain path expansion scheme, end-to-end link disjoint path pairs can be

    50 obtained. Also, traffic engineering (TE) concern is applied in this multi-domain environment.

    Routing overhead and computational complexity is reduced to get better scalability and privacy. The paper is organized as follows. Section 1 formulated integer linear programming functions for link-disjoint paths problem, aiming to minimize the blocking rate. Section 2 proposed heuristics for multi-domain disjoint path provisioning with TE concerns. Performance evaluation is

    55 presented in Section 3, followed by conclusion in Section 4.

    1 ILP formulation for Link-Disjoint Path in Multi-Domain Network

    ILP has been widely used in network optimization. By setting up objective function and constraints, optimal solution can be obtained, which can be used as performance upper bound. Comparing this optimal solution with proposed heuristic, we can estimate the performance of

    60 proposed heuristic and find the gap to upper bound. Although ILP formulation for protection have [6]been studied, the existing formulations are setting up for wavelength routing and aims at minimize the total number of wavelengths used on all the links in the network. This paper, proposed another ILP formulation for link-disjoint path protection for bandwidth routing optical network, from the prospective of blocking rate. Instead of minimize the total wavelengths used for

    65 both primary and backup paths, the objective function is set to maximize the number of successfully routed connections, as well as minimize resource usage. Constraints are also adjusted accordingly.

    In order to corporate the multi-domain network environment, hierarchical ILP solving is introduced. It is not a fair comparison to run ILP on a flattened multi-domain network, will all

    70 global topology information, while the heuristic can only have partial global information. In order to make the comparison on a fair base, hierarchical ILP solving is introduced in 1.2.

1.1 ILP Formulation

    Before present the ILP formulation, representation is introduced. A bandwidth routing network is represented as a graph G = (V, E), where V is the set of nodes and E set of edges

     75 (links). Let N be the number of end-to-end flows or connection requests. Each request ischaracterized by a 3-tuple (s, d , r) , where sdenotes the source node, d denotes the n n n n n ndestination node and ris an integer number to represent the required bandwidth units. Usex n ij th as a variable for primary routes of the request, represent the number of bandwidth units n n n carried on link (i, j) . Similarly, define variable for backup routes. p is a binary variable to y ij ij th n 80 represent whether or not link (i, j) is passed by the primary routes of the nrequest. Define b ij

     {0, r} as the number of bandwidth units allocated forsimilarly for backup routes. Define f ?n n th ' primary route of the nrequest, similarly define f ? {0, r } for backup routes. The objective n n

    function is to maximize the number of successfully routed requests. Notice that, a request will be considered to be successfully setup only when both primary and backup routes are allocated.

     f n n n 85 MAX w ?w ( x + y )n ? N , (i, j) ? E(1) ?1 ? ij ij2 r n?N n?Nn

    - 2 -


    ?; if f i = s n n

    ?n n

    x? x= ? ; f if i = d ?n ? N , (i, j) ? E ? ij ? ij n n(2)

    ? 0; otherwise j:(i , j )?E j:( j ,i )?E

    ? ; if f i = s ? n n

    ?n n

    y? y= ? ; f if i = d ?n ? N , (i, j) ? E ? ij ? ij n n(3)

    ? 0; otherwise E j:( j ,i )E j:(i