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

By Jon Powell,2014-09-09 11:26
13 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 , j )??

    ( x + y ) ? c n ? N , (i, j) ? E (4) ? ij ij ij


    n ? N , (i, j) ? En n x y (5)

    n n?N ij n + ? 1 nij r n r n 90 x? {0, r},(6)n ? N , (i, j ) ? E ij n n (7) n ? N , (i, j ) ? Ey ? {0, r },ij n n (8)f ? {0, r},n ? N , (i, j ) ? E n Function (1) is the objective function, which aims at maximizing the number of successful

     wand ware user defined constant, to impose connections while minimizing resource usage. 1 2

    weight on success rate and resource usage. Functions (2) and (3) set the flow conservation for 95

     primary and backup routes. Function (4) imposes the bandwidth constraints. Function (5) set up the link-disjoint restriction. Function (6), (7) and (8) restrict the flow and sub-flow carried on each

     link to be either 0 or the required bandwidth. 1.2 Use ILP Hierarchically in Multi-Domain Networks

    In order to compare ILP optimal solution and heuristic performance on a fair base, method 100

     to solve ILP hierarchically is presented. Specifically, firstly solve the ILP on inter-domain topology to get a loose routing sequence. Then feed the result as intra-domain requests and solve

     the link-disjoint path in related domain. Finally, concatenate all the intra-domain solution along loose routing sequence and calculate blocking rate.

    105 2 Diverse primary/backup path computation heuristic with TE

    Novel heuristic for link-disjoint path computation is proposed in this section. Before

    presenting the heuristic, the requisite notation is introduced. A multi-domain network is comprised

    i i of D domains, with the i-th domain having nnodes and bborder nodes, 1?i?D. This network is iiiii i iii modeled as a set of sub-graphs, G(V, L), where V={v, v, …} is the set of nodes and L={l}1 2 jk iiiii110 is the set of intra-domain links in domain i (1?i?D, 1?j,k?n), i.e., l to v with is link from v jjk k iiiimaximum and available capacity Cand c, respectively. The inter-domain link connecting jk jkijijborder node v in domain i with v in domain j is also denoted as l with maximum and m km k ijijijavailable capacity Cand c, respectively, 1?i,j?D, 1?k?b, 1?m?b. Working path iskm km

    - 3 -


    ijrepresented by w , where i, j represent source and destination domain respectively, m, n mn

     115represent source node and destination node in related domain. Similarly backup path isij represented by b. mn In order to apply this heuristic, PCE nodes should have full access to the routing database,

     which have full internal link-state information and partial global information. A more scalable link-state exchange scheme is used to get these partial global information, which will be detailed

    later. Resources reservation protocol (RSVP-TE) is used to setup signaling. Only 120

    - 4 -


     bandwidth-routing IP/MPLS networks are considered. There are 2 phases in this computation scheme. Firstly the diverse primary/backup LR

     sequences are computed. Then the intra-domain extension is done by signaling. Since link disjoint concept is applied in both phase, this heuristic is referenced as Dual LD for convenience. Three

    125 key innovations are used here to improve the multi-domain protection: 1) inter-domain

     load-balancing across the global topology is achieved with routing strategies, 2) introduce Suurballes algorithm into inter-domain LR computation, 3) signaling provisions to maintain intra-domain path diversity when encountering domain overlaps, as well as overcoming trap topology.

130 2.1 Disjoint Loose Route Computation with TE Partial inter domain visibility is the foundation of LR pair computation. Topology abstraction and hierarchical routing have been well studied to provide this partial global visibility. The

     focus of this paper is not developing new topology abstraction scheme, but using appropriate existing scheme to help computing link disjoint route pairs. Considering both scalability and

    privacy, a widely used abstraction algorithm, full mesh abstraction is adopted. In order to address 135

     traffic engineering consideration, weigh scheme in used in topology abstraction. For the links inijH(U,E), the weights ω is computed as equation 9. km

    ij uC ij mn (9)w= mn ij c +ξ mn where u is a constant defined by user. Thus more congested links have higher cost and ξ ? 0

    to avoid division-by-zero. After assigning costs to links, K-SP routes are computed between any 140

     border node pairs in the same domain, the average bottlenecks are used as capacity and average path costs, which can be obtained by OSPF-TE, are used as costs for these abstract links between 2 ), a notable reduce comparing to the scheme in [3]. border nodes. The computational cost is O(N

    (This scheme is referenced as Sprintsons Scheme for convenience, naming after the author). The

    145 information collected via full-mesh abstraction is denoted here via a global topology graph,

    iH(U,E), where U is the set of border nodes, U=?{B}, and E is the set of higher-layer links. i iji i Namely, E=?{l} U ? {E}, where Edenotes the set of abstract links in domain i. PCE, whichkm i a a

     have full access to this information, can compute the diverse routes.

     Fig.1 Trap topology example 150 With the abstracted topology H(U,E), the inter-domain disjoint loose route can be calculated. Suuballes algorithm is introduced to inter-domain link disjoint route computation. It is an algorithm for finding two disjoint paths in a nonnegatively weighted directed graph, so that both

    155 paths connect the same pair of vertices and have minimum total length. In the inter-domain LR

    computation phase, Suurballes is introduced to avoid trap topology. For example, in figure 1,

    when shortest path is computed, link disjoint for the shortest path does not exist. Thus, the

    - 5 -


     computation for two link-disjoint paths fails. However, link disjoint paths , e.g. A->C->D->F and A->B->E->F does exists. Using Suurballes algorithm, link disjoint paths can be computed

    successfully in this trap situation. Thus decrease the path computation failure rate. The overall 160

     steps for link disjoint LR pair computation are summarized in figure 2.

     Fig.2 link disjoint LRs computation with Suurballes algorithm

    165 2.2 Intra-Domain Path Expansion with Suurballes algorithm After the diverse LR pair computation, the source node initiates the RSVP-TE signaling and do explicate route(ER) expansion to get the specified intra-domain routes and reserve resource for

     the full end-to-end path. Steps for this phase are summarized in figure 3. 170Fig.3 Intra-Domain path expansion with Suurballes algorithm Surrballes algorithm here is used to avoid trap topology. However, originally Suurballes algorithm is designed for computing link-disjoint path pairs with same source and destination node. In the proposed heuristic, the ingress nodes and egress nodes in one overlapped domain are

    175 usually different. In order to apply Suurballes algorithm for link disjoint path expansion for overlapped domain, we can add two virtual nodes to the intra-domain topology and force it to meet the same-source, same-destination restriction. Specifically, one virtual node is added and connected to both ingress nodes, and another is added and connected to both egress nodes.

     3 Simulation and Performance Evaluation

    Simulation is done with two network topology with different traffic scenarios. Firstly, in 180

    order to estimate the heuristic performance gap from optimal ILP solution, simulations over a

    - 6 -


     network consist of 6 domain is done. In this simulation, due to the intrinsic of ILP, partial static traffic model is used. Then, a simulation with a more realistic dynamic traffic model is done over a

     modified NSFNET.

185 3.1 Simulation in a small scale network In order to incorporate ILP to get optimal solution, partial static traffic model over a 9 domain network topology (see figure 4) is used. A relative small network is used due to the

     computational complexity of ILP(NP complete). Considering the static intrinsic of ILP, partial dynamic traffic model is adopted. Connection requests are added into the network gradually

    without tearing down. In other words, there are only traffic coming into the network but leaving 190

     traffic. Specifically, ILP constraint functions are setup over the topology using PuLP_or, a LP modeler in Python. With randomly generated request, the problem is solved in a hierarchical way

     described in section 1.2. The same requests are then feed into network simulation tool. In order to mimic the partial static situation, the connection holding time is set into infinity. Simulation

    results are plotted in figure 5 and figure 6. 195

     Fig 4. A 9 domain topology with small domain size

    From figure 5 and 6, we can see that the performance gap between ILP and the Sprintsons

    scheme is big. Although [3] proves that this scheme is optimal, however, it rely on in-time update 200

     of the domain state. This is hard to achieve in real world network environments, especially when 4the topology computation/update overhead is very high (O(N) ). As we can see in the plots, the

     scheme degrades greatly due to the domain state update delay. With this partial static traffic, the performance of our proposed Dual LD scheme is very close to Sprintsons scheme.

    Notice that in figure 6, the hop counts decrease with the total number of connection requests. 205

     Thats because of the traffic model we use in this simulation. Since no connection is removed from the network, the network gets saturated easily. For ILP, the objective is to maximize success

     rate, so with higher load the requests need longer paths are abandoned. For network simulation, after adding sufficient traffic, the residual network resource is limited. Connections can be failed

    at each intermediate link. Since longer path have higher aggregate fail probability, more shorter 210

    paths are setup successfully.

    - 7 -


     Fig.5 Comparison of blocking rate

     215 Fig.6 Comparison of average path length(hop counts) 3.2 Simulation in NSFNET In order make a more realistic comparison, the proposed multi-domain protection solution

    220 and the scheme in [3] are also simulated in larger scale network with fully dynamic traffic. Here

     NSFNET topology is used as domain topology. The intra-domain topologies have node number between 7 and 10, with averaged node degree of 3.5. Capacities are set to 10Gbps for both intra

     domain and inter domain links. Basic bandwidth unit is defined as 200Mbps. The requested bandwidth varies from 200Mbps to 1Gbps (1 to 5 units), in increment of 200Mbps. Requests are

    generated randomly between nodes with exponential holding time and inter-arrival time. 225

    - 8 -


     Fig.7 Comparison of blocking rate

     Fig.8 Comparison of average path length (hop counts)


     Simulation results with partial static and full dynamic traffic model both show that the blocking rate of the proposed Dual LD scheme is slightly higher than the Sprintsons scheme. One reason is that the Sprintsons Scheme in [3] degrades greatly in realistic network setting with non-zero domain state update time. On the other hand, the Dual LD scheme, although cannot

    235 guarantee to be end-to-end link disjoint at the LR computation level (e.g., two abstract link can

     share some intra-domain physical links), actually most of the computed path pair turn out to be link disjoint. Thats because the intra-domain topology usually has enough connectivity, e.g. interior nodes and node degree, to provide intra-domain link disjoint paths. The Sprintsons scheme in [3], pay much higher price to give that slightly lower blocking rate. The topology 4240 abstraction/update overhead is O(N) , which is much higher than the scheme proposed in this

    paper. It is very doubtable that this gain worth the computational and updating overhead or not.

    Despite this complexity, it may also violate network carrier’s privacy policy. Also, simulation

    results with simple node topology abstraction are plotted. Compare with full mesh abstraction, the

    blocking rate is much higher. This demonstrates the effectiveness of proposed load-balancing with

    - 9 -


    full mesh abstraction. Overall, the proposed Dual LR scheme, which gives much lower 245 compute/update overhead can achieves comparable performance, and is more suitable for real

     work implementation due to scalability and privacy concerns. 4 Conclusion In this paper, a novel diverse path protection solution using hierarchical routing is proposed

    250 for multi-domain networks. Aiming at end-to-end link-disjoint protection, a two phase

     link-disjoint route computation is introduced. Suurballes algorithm is used in both inter-domain LR computation and intra-domain link disjoint ER expansion, to avoid trap topology and increase

     computation success rate. Comparison between ILP solution and performance of scheme in [3] show that the scheme in [3] is far from optimal with realistic network settings. Our proposed

    scheme gives a very close performance quality as the scheme in [3]. With slightly decrease in 255 42 performance, the computation/update overhead is decreased from O(N) to O(N). Also the proposed heuristic reveals less intra-domain information, thus gives more privacy. Overall, the proposed framework is more practical than [3] from a routing prospective.

     References260 [1] T. Takeda, et al, "Diverse Path Setup Schemes in Multi-Domain Optical Networks"[Z], IEEE BROADNETS 2008, London, England, September 2008. [2] T. Takeda, et al, "Analysis of Inter-Domain Label Switched Path (LSP) Recovery"[Z], IETF RFC 5298, August 2008.

    265 [3] A. Sprintson, et al, "Reliable Routing with QoS Guarantees for Multi-Domain IP/MPLS Networks"[Z], IEEE INFOCOM 2007, Anchorage, AL, May 2007. [4] D. Troung, B. Thiongane, "Dynamic Routing for Shared Path Protection in Multidomain Optical Mesh Networks"[J], OSA JoN, Vol. 5, No. 1, Jan. 2006, pp. 58-74. [5] D. Troung, B. Jaumard, "Using Topology Aggregation for Efficient Segment Shared Protection Solutions in

    270 Multi-Domain Networks", IEEE Journal of Selected Areas in Comm., Vol. 25, No. 9, December 2007, pp. 96-107. [6] Rudra Dutta, Ahmed E. Kamal, George N. RouskasTraffic Grooming for Optical Networks: Foundations, Techniques and Frontiers[Z], New York: Springer-Verlag, August 2008


     梁凯乐?王宏祥275 ;北京邮电大学信息与通信工程学院?北京 100876 摘要, 现今社会?信息技术的重要性日益提升?网络生存性问题受到越来越多的关注。单 域的故障保护及恢复机制已经得到了深入研究。然而?将这些机制应用到多域光网络中?任 然面临着很多挑战。本文在路由开销和计算复杂度较低的前提下?提出了一种考虑了流量工 程的不相交链路对保护机制?为可能发生的故障提供端到端保护。以最小化阻塞率为目标的 280 整数线性规划方程及相关约束条件被提出?并将其应用于多域网络中?获得最优解?用来与

    本文所提出的机制的仿真结果做比较。 关键词,不相交链路对!保护!多域网络!整数线




    - 10 -

Report this document

For any questions or suggestions please email