Đề tài Shared Protection for Multi-Domain Optical Mesh Networks

r node and no more nodes are recorded because the backup path does not pass through AS 3. B13 linked to B8 continues the same process as B6. Furthermore, this time some nodes to exclude are added into the exclusion list because backup path goes though AS 4 also. And so on until B is reached. After that, the working path is set up. Next, a similar signaling process carrying the exclusion list begins from A, looking for backup segments within every AS in the AS path of the backup path. Certainly, all nodes in the exclusion list must be excluded in the search. The backup path is after that reserved. This search assures that the two paths are node-disjoint but as we can notice, no information about the possibility of sharing bandwidth with other backup paths is taken into account. Furthermore, AS paths are calculated by using the algorithms in [Suurballe74] [Suurballe84] [Bhandari99], which have no ideas of shared protection. Furthermore, backup paths are reserved without considering the possibility of reusing the bandwidth of other backup paths. Obviously, no backup resource sharing is supported and the protection can be classified as dedicated protection. 36 2.3.1.3 Failure Notification The original document does not mention the failure notification. Since this is path-based protection, the failure notification process should begin from the node adjacent to the failure; propagate along the failed lightpath in two directions until reaching to the two end nodes. Of course, this is a long notification over multiple AS’s. 2.3.1.4 Backup path setup signaling As for notification, backup path setup is not clearly mentioned in the cited document. However, because the protection is proposed for MPLS, the backup path reservation process at the end of the path computation also includes backup LSP1 setup. No signaling is necessary to activate backup paths after failures. If we apply this approach to the optical network, backup paths can be set up before failures because they are dedicated for their working paths. 2.3.2 Multiple Single-Domain Protections Approach We refer to the work of Akyamaç et al. presented in [Akyamac02a] as “Multiple single domain protections”. This work is a further improvement of the work in [Ou01]. 2.3.2.1 Protection Model The work deals with a multi-domain optical network that is similar to ours. However, it considers that the set of border nodes and inter-domain links of two neighboring domains also forms a domain. One domain connects to another by at least two gateway nodes: primary and secondary gateways (Figure 14). A segment-based protection with link-disjoint segments is proposed. End-to-end lightpath consists of smaller lightpath segments within the domains it crosses. Segments begin and end at primary gateways. Each working segment has a backup segment bounded in its domain. The two segments join at the primary gateway. When the working segment fails at a cable or an intermediate node, the backup segment is activated by the primary gateways. Thus, routing and restoration is strictly limited to each domain and independent from one domain to another. The recovery will be faster than that of CCAMP’s approach. However, when the primary gateway fails, “the secondary gateway is used to restore against the failure of the primary gateway node (handle via lightpath re-provisioning)” (cited from the original document). That means a new end-to-end backup path is calculated. 1 Label Switched Path 37 Thanks to the independent recovery in different domains, this solution can protect against multiple simultaneous failures in various domains. Since working and backup segments are bounded in the same domain, the resource sharing between backup segments of the domain can be enabled easily by using single-domain path computation algorithms for shared protection. Figure 14: Multiple single domain protections approach (from [Akyamac02a]) However, the protection scheme strictly requires that working and backup segments cross in parallel over the same domains. This limits the choice of backup segments implying increasing blocking probability due to resource insufficiency for the two segments, which must also be node-disjoint. Meanwhile, there are still other backup segments crossing other domains than those of the working segment and they can protect the working segment. Further more, the lightpath re-provisioning on the fly, in the case the primary gateway node fails, transforms the proposed “protection” into “restoration”. This implies a QoS declining in terms of recovery guarantee as well as restoration time. Supposing that the alternative path using the secondary gateway of the failed primary gateway does not exist, the lightpath cannot be recovered and the affected traffic must be dropped. In fact, border nodes are intensive-traffic points. Multi-domain lightpaths transit more frequently through border nodes than internal nodes. Low quality of recovery at border nodes may cause a severe impact. According to us, restoration for border nodes is inadequate. 2.3.2.2 Path Computation The original document does not mention the end-to-end path computation. We know only that working and backup segments are computed within each domain as a single-domain 38 lightpath. Therefore, all path computation methods for single-domain shared protection can be applied to identify working and backup segments between gateway nodes. It remains always to identify the path of the gateways of the end-to-end path. 2.3.2.3 Notification and Backup Path Setup Signaling As for path computation, the notification and backup path signaling are limited to the scale of one domain. Obviously, this approach offers a much faster notification and signaling than CCAMP. 2.3.3 SRLG-Disjoint Routing for Multi-Segment Protection Approach S1 1 2 D 43S2 a) Physical layer topology SRLG #1 SRLG #3 SRLG #5 SRLG #4 SRLG #2 S1 1 4 D 23S2 b) Optical layer topology SRLG #1 SRLG #4 SRLG #3 SRLG #5 SRLG #6 SRLG #4SRLG #2 common conduit SRLG #6 Figure 15: Example of two node-disjoint paths that belong to the same SRLG In this section, we review the approach proposed by T. Miyamura et al. in [Miyamura04]. The work is reported providing an SRLG-disjoint routing algorithm for multi-segment protection in inter-area networks. There are two main contributions. First, routing for multi-segment protection is defined. Second, the routing guarantees that two working and backup paths are SRLG-disjoint. The condition SRLG-disjoint is more general than the link-disjoint constraint at the optical layer because the physical and optical topologies may be different. Two fibers that are node disjoint at the optical layer are not necessarily SRLG disjoint physically if they are bundled in the same conduit. A failure at the common conduit causes the failures of both fibers even though they are node-disjoint. Figure 15 shows an example of such paths: S1-1-4-D, S2-3-2-D. The links that have the same risk are assigned the same SRLG identification. 2.3.3.1 Protection Model Before talking about the protection model, let us introduce the inter-area network model referred to by this work. Initially, the multi-area MPLS network, which is seen from a 39 routing viewpoint as a multi-area OSPF network [Moy98], is referred to. The multi-area OSPF network contains one backbone and various non-backbone areas as depicted in Figure 16. Border routers connect directly to different areas. All border routers belong to the backbone area. The connectivity of the backbone area is maintained by configuring virtual links between the border routers of the same area. The concrete routes of a virtual link cross internal routers of one area, thus they are invisible from the border routers of the other areas. For example, in Figure 16, B4 does not know the concrete routes of the virtual link B2-B3. The topology of the backbone dictates the backbone paths used between areas [Moy98]. Those paths are in fact the virtual link paths. backbone area border router virtual link internal router B1 B2 B4 B5 B3 S D area 4 area 1 area 2 area 3non-backbone area a physical route of the virtual link B3-B4 Figure 16: Multi-area network However, the authors based their work implicitly on a simpler network model to build their path computation algorithm. In that model, two non-backbone areas reach each other without passing through other intermediate non-backbone areas (Figure 17). This model may be suitable for modeling the metro/core networks relationship but does not reflex general multi-area networks. T. Miyamura et al. propose a special Segment-based Protection scheme (Figure 18). For protecting an end-to-end working path (the path 1-2…-9 in the figure), an initial end-to- end backup path is searched for (1-9), which is not necessarily SRLG disjoint with the working path. If the two paths are disjoint, the backup path protects the working path. Otherwise, the working path will be divided into two at the head-end node of the SRLG- joint link (link 3-4 for example). A backup segment for the segment between the SRLG- joint node and the destination (segment 3-..- 9) is searched. When the SRLG-joint link fails (link 3-4), this new backup segment will be used. If the found segment still shares risk with its working segment, the working segment will be divided further in the same way (at node 5 for instance) and a new backup segment will be found. 40 Therefore, different backup segments, which all end at the destination node, protect the end-to-end working path. When a failure occurs somewhere on the working path, the backup segment encircling the failure will be activated. backbone area B1 B2 B4 B5 S D area 4 area 1 initial working and backup segments Figure 17: Multi-area network viewed by T. Miyamura et al. Figure 18: Multi-segment protection 2.3.3.2 Path computation T. Miyamura et al. call the source area the “initiator area”, and the destination area the “terminator area”. For example, if we are looking for a path from S to D in the network in Figure 17, the initiator area is area 1, the terminator area is area 4. The path computation begins by identifying the initial working and backup path. Each path consists of two segments, the first segment is in the initiator area and the second segment is in the backbone and terminator areas. One border router in the initiator area is chosen to calculate two segments from the source (S in Figure 17) to two egress border routers of the initiator area (B1, B2). One segment is for the working path (bold line) and the other is for the backup path (long dashed line). 1 2 3 4 5 6 7 8 9 Working segment 1 Working segment 2 Working segment 3 Initial backup path 41 Next, a border router of the terminator area calculates the second segments from the above egress border routers (B1, B2) to the destination. According to the authors, the computation is feasible because the border router of the terminator area has the complete view of the backbone and terminator areas. We then have two pairs of initial working and backup segments, the pair in the initiator area and the pair in the backbone and terminator areas. The working and backup segments of each pair need to be SRLG disjoint. To resolve this, the border router of the initiator area applies the segmentation method described in the previous session to the first working segment. Similarly, the border router of the terminator area does the same with the second working segment. As a result, the working segments are split smaller and multiple backup segments are generated. Although this algorithm is reported to be able to find the working segment and all backup segments necessary, we found that there is an error in the way the authors saw the network. The authors supposed implicitly that working and backup paths never cross any intermediate non-backbone area. Or, the border routers of the terminator area can always see the physical routes of paths in intermediate areas. Consequently, this router can easily compute the working and backup segments in the intermediate areas and can check if they have the same SRLG. In fact, with the general network model given in Figure 16, working and backup segments may pass through multiple intermediate areas. The border routers of the terminator area can rather see the virtual links crossing these areas than their concrete routes. For example, border routers of the terminator area do not see the routes of the segments in the areas 2, 3. Thus, they cannot check the SRLG disjoint relationship of working and backup segments there. Furthermore, in this protection model, one working segment contains another. The amount of protection resources needed is then multiplicative. According to the authors, different backup segments of the same working path can share bandwidth on the links they pass through. This leads to better network resource utilization. However, the path computation algorithm does not pay any attention either to this possibility or to the possibility of sharing bandwidth among backup paths of different working paths. The bandwidth utilization is thus far from efficient. 2.3.3.3 Notification and Backup Path Setup Signaling The original document does not describe the notification and backup path setup signaling. However, we notice that the notification time depends on the length of the working segments containing the failures. It may vary from very short, if the failure is near to the 42 destination node, to very long, equal to the length of the end-to-end lightpath, if the failure is near the source node. Synthesis Table 3 recapitulates the three protection approaches specific to multi-domain networks that we have reviewed. The Path-based Protection approach of CCAMP protects all node and link failures but consumes too much protection resource because the absence of shared protection. Moreover, it suffers from a long restoration. The “multiple single-domain protections” approach does things better. It restricts the protection in the scale of one domain, so has simpler path computation, shorter notification and backup path setup signaling. It enables shared protection within a domain and then uses fewer protection resources. However, it offers an end-to-end restoration in the case of border node failures. The quality of recovery declines dramatically. Moreover, it poses the strong constraint that one domain must connect to another at least 2 gateways. Protection model Backup resource sharing Notificatio n scale Backup path setup scale Border node recovery Path based protection of CCAMP Dedicated path-based No End-to-end N/A Protection Multiple single- domain protections of Akyamaç et al. Shared segment- based Yes Domain scale segment Segment scale Restoration SRLG-disjoint routing for Multi- segment Protection. Dedicated segment- based Partially Various scale N/A Protection Table 3: Recapitulation of inter-domain protection approaches The “SRLG-disjoint routing for Multi-segment protection” approach of Miyamura et al provides a Segment-based Protection. The objective is to find a set of backup segments that SRLG disjoint with its working path. Nevertheless, their network model is really a particular case of multi-area networks. In addition, the protection scheme requests too many protection resources for a working path while supporting limitedly shared protection. The resource utilisation is still far from efficient. Therefore, there is no protection that i) protects all nodes and links of multi-domain lightpaths and ii) supports shared protection in the same time. On the other hand, the existing shared protection solutions limit themselves to single-domain networks with the assumption that the complete network topology and even resource allocation information are available at a computation center. We can conclude that Shared Protection for multi- domain lightpath is still an open problem. 43 Chapter 3 Proposal 3.1 Problem Statement and Objectives Since shared protection for multi-domain lightpaths is still an open problem, we will try to resolve it. Concretely, we deal with the problem of shared protection against both link and node failures for multi-domain optical mesh networks that have dynamic traffic demands. We are interested in the single failure scenario where there is only one failure at a time in the overall network. In such a failure scenario, the protection we look for will guarantee 100% protection. However, multiple simultaneous failures may still be recovered with lower guarantee degrees. The main differences between the problem of protection for multi-domain network and that for single-domain network are in the former: iii) The working and backup paths are longer resulting in a longer notification and signaling. iv) The complete information about the internal topology and resource allocation of any domain is unavailable for the exterior. Consequently, no node has the global network information. From the literature study, we demonstrated that the existing shared protection approaches are not applicable for multi-domain networks. This is because they require the knowledge of the complete network topology and even resource allocation on each link to be available at a computation center. On the other hand, the existing solutions for real multi- domain networks either do not support shared protection and have long recovery process as CCAMP’s approach (see 2.3.1), or leave border nodes unprotected and require high connectivity between domains as in [Akyamac02a] (see 2.3.2). In the present research, we look for a better solution in terms of network resource utilization, recovery time and node protection. The difficulties reside in the complexity of path computations (for shared protection) and the scalability constraint of multi-domain networks. Our concrete tasks are then: • Look for a protection model that covers all node and link failures and that can limit the notification and signaling scale. • Propose a path computation method that supports shared protection among backup paths and is scalable for multi-domain networks. In addition, the total 44 resource cost of the two paths must be reduced. The path computation will be a compromise between the scalability and resource minimization objective. • Define the accompanying path request signaling process. • Define the accompanying notification and backup path setup signaling processes. All these objectives must be achieved under the following constraint of multi-domain networks: • Invisibility of domain’s internal topology and TE information from outside 3.2 Proposed Approach As we dealt with the multi-domain network protection problem, before presenting the approach, let us introduce the multi-domain network model that we will work with. 3.2.1 Multi-Domain Network Model Notice the weakness of the former work in [Miyamura04] on the network model assumption; our multi-domain network model is more general. The network contains multiple single- domain optical mesh networks; each one is independent of the others in routing and resource management. A domain connects to its neighboring domains through inter-domain links associating the two domains’ border cross-connects. One domain may reach to another via intermediate domains called transit domains. Domain Domain Domain Domain inter-domain link border node virtual link A B internal node Figure 19: Inter-domain topology seen by border node A or B Every node of one domain has the complete knowledge of the domain. In contrast, due to the domain autonomy, the security problem and the scalability constraint, the complete 45 topology and TE1 information, including resource availability and resource allocation, of one domain is hidden from outside. The border nodes rather than internal nodes know the connectivity between domains. Border nodes see the external domains as a set of border nodes inter connected by virtual links, which represent the possible routes between the border nodes. The virtual links represent the capacity of these routes through its TE information, which is the aggregated information of those routes. (Readers are referred to [Hao00] [Chung01] for some basic concepts, issues and techniques about such aggregation). Thus, a border node views the multi-domain as the combination of: its domain and the border nodes, inter-domain links and virtual links of other domains (Figure 19). We refer to the topology and resource allocation viewed by a border node as inter-domain topology and inter-domain resource allocation. Our network model is actually similar to the GMPLS overlay model [gmpls] or ASON architecture [ason]. The network makes use of intelligent OXCs as cross-connects, which are sub-wavelength switching and wavelength conversion capable. OXCs are supposed to be able to provision non-contiguous bandwidth. The optical network is supposed to have an IP control plane and every OXC is assumed configurable through the control plan. This assumption is quite realistic because the modern OXCs such as ONS [ons] of CISCO System, OPTera Metro [optera] of Nortel Networks, etc., have configuration interfaces using TL1 [TL1] or SNMP [snmp], which are controllable from IP network. 3.2.2 General Approach 3.2.2.1 The choice of the protection model In studying different protection schemes, we learnt that only Shared Segment-based Protection offers simultaneous backup resource sharing, short notification and short backup path setup signaling. Its variation, Overlap Segment Shared Protection (see 2.1.4.4 and 2.2.2), in addition, protects every node and link. The Overlap Segment Shared Protection (OSSP) model meets our requirements perfectly regarding the recovery quality and resource utilization. Thus, we choose OSSP as the base of our protection. Working lightpaths will be divided into overlap segments and protected by backup segments. The employment of OSSP itself makes our solution better than CCAMP in resource utilization efficiency and notification time, and [Akyamac02a]’s in border node protection. 1 TE : Traffic Engineering 46 3.2.2.2 Path computation problem Although OSSP is chosen as the protection model, there are still a lot of works to do because the path computation for OSSP for multi-domain networks is a challenge. The computation missions are i) to search for working path, ii) to divide the working path into segments, and iii) to seek for backup segments while allowing them to reuse resource of existing backup segments. The computation problem is even more difficult than that of Path-based shared protection, which is already an NP-hard problem (see Section 2.2.1.2 for the algorithms and the complexity of this problem). Moreover, the prior path computation algorithms for OSSP are too specific for single-domain networks (see Section 2.2.2). They require a global view of network topology or even of resource allocation, so cannot be applicable for multi-domain networks. A new path computation algorithm is necessary. Thus, we propose here an instance of OSSP with a new computation scheme that specifically fit to multi-domain networks and a tailored segmentation supporting this computation. Our path computation is inspired by the idea of dividing the path computation into two levels from the CCAMP’s approach in [Dachille04a]. We call the two computations: “inter-domain level computation” and “intra-domain level computation”. The Inter- domain level computation operates on inter-domain topology and looks for the sequence of domains that working and backup paths will traverse. The Intra-domain level computation searches for the internal paths within each domain with the single-domain topology. Thanks to this, the computation will be scalable for multi-domain networks. However, our computation algorithms at each level are quite different to those of CCAMP. This prior computation is for dedicated path-based protection that means it seeks for an end-to-end working path a dedicated end-to-end backup path. Contrarily, our path computations seek for working and backup segments and promote the sharing of backup resource among backup segments. Moreover, the computation of CCAMP (for MPLS networks) bases mainly on the topology information and seeks paths without any bandwi