Transcription
V International Workshop on Reliable Networks Design and Modeling (RNDM 2013) co-located with ICUMT 2013Optimum Logical Topology Routing in anIP-over-WDM Optical Network and Physical LinkFailure Localization: An Integrated ApproachTachun LinZhili ZhouDept. of Computing and Technology IBM Research CollaboratorySingaporeCameron UniversityEmail: zhili@sg.ibm.comLawton, Oklahoma 73505Email: tlin@cameron.eduGuoliang XueUniversity of OklahomaNorman, Oklahoma 73019Email: thulasi@ou.eduArizona State UniversityTempe, ArizonaEmail: xue@asu.edurouting in the IP-over-WDM network, and (2) failure localization in the optical network. Survivable logical topology routingin an IP-over-WDM optical network is a mechanism whichguarantees the connectivity of the logical network and hencemaintains continuous flow and operability after a networkfacility (link or node) failure. The survivable routing problemhas been intensively studied. The research works related tofailure localization focus on the optical network. They combine detection sensors and their corresponding monitor trails(m-trail, monitor cycle, and monitor path) to provide a uniquesignal to identify optical fiber failures. Previous works in theliterature considered augmentation of the logical topology withadditional links to guarantee the existence of a survivablerouting.The likelihood that a logical topology may not admit asurvivable mapping and the need for optical failure localizationmotivate the study in this paper. We provide an integratedapproach to survivable IP-over-WDM routing and opticalnetwork failure localization problems. We aim to generatethe optimum routing (to be defined later) within the currentnetwork structure, which guarantees the connectivity of thelogical network under most scenarios of optical link failurewithout any extra logical network augmentation. Meanwhile,the failure of the optical links would disrupt the communication between logical node pairs, and the corresponding brokenlightpaths could help to detect the optical fiber failure throughloss of signal or communication. Therefore, the lightpaths havethe functionality of the monitoring paths [1][2]. Comparedwith monitoring paths in the optical network, lightpaths wouldnot involve extra monitoring cost. If appropriately designed,most physical link failures would not cause disconnection ofthe logical network. So, for failure localization we concentrateon optical links which would disconnect IP communicationunder a given optimum routing.On the other hand, the number of lightpaths is equal to thenumber of logical links. They may not be sufficient to providea unique detective signal for a physical link failure. Hence, wewould still involve monitoring sensors and their correspondingpossible monitoring trails in the optical network to localize theAbstract—The survivable logical topology routing problem fora given IP-over-WDM network is to map each logical link into alightpath in the physical network which guarantees connectivityof the IP network after any physical link failure. Such asurvivable routing is said to protect the logical network againstall single physical link failures. But, it is possible that a logicaltopology may not admit a survivable routing. In view of this, wedefine a logical topology routing to be optimum if this routingmaximizes the number of single physical link failures that donot disconnect the logical topology. First, we give a mixed integer linear programming formulation to determine an optimumlogical topology routing. The failure localization problem is tolocalize the single physical link failures which disconnect thelogical network under a given optimum routing. Given a setof monitoring trails and the lightpath routings in an optimumrouting, we give a mixed integer linear programming formulationto determine an optimum routing and the corresponding failurelocalization. We also propose a heuristic approach for theseproblems to handle large scale IP-over-WDM networks.Index Terms—Optical communication, IP-over-WDM network,optimal routing, failure localization, graph theory.I. I NTRODUCTIONIP-over-WDM network is a two-layered network where anIP (logical) network is embedded onto a WDM (physical)network. IP routers and OXCs correspond to the logicaland physical nodes. Links connecting the nodes in a logicalnetwork are called the logical links, and the physical links arerealized via optical fibers. The logical nodes are commonlyassumed to have corresponding nodes in the physical network.On the other hand, not all physical nodes may exist inthe logical network. A router-to-router link is implementedthrough a wavelength on a path between two end nodesin a WDM network bypassing opto-electro-optic (O-E-O)conversions on intermediate nodes along the path. This pathis called a lightpath. Each optical fiber may carry multiplelightpaths, hence a failure on an optical fiber may have acascading effect causing failures on multiple logical links,resulting in a huge amount of data traffic (terabytes/sec) loss.Previous research works to address optical fiber failures aremainly along two directions: (1) survivable logical topology978-1-4799-1177-6/13/ 31.00 2013 IEEEKrishnaiyan Thulasiraman82
V International Workshop on Reliable Networks Design and Modeling (RNDM 2013) co-located with ICUMT 2013physical link failure which could disconnect communicationin the IP network.Summarizing, in this paper, we address a new problemwhich aims to utilize facilities in the current IP-over-WDMnetwork to provide an optimum routing for IP demandswhich keeps connectivity in the IP layer under most scenariosof the physical link failure, and localize all physical linkswhose failures cause the disconnection in the IP network.The paper is organized as follows. In section II we reviewthe current literature relating to survivable logical topologyrouting and physical link failure localization problems. Insection III we define the concept of optimum logical topologyrouting and related concepts. We illustrate the concepts withexamples. In section IV we present ILP formulations for threeoptimization problems. The first is to determine an optimumlogical topology routing. Given an optimum logical topologyrouting and a set of monitoring trails, the second problemis to determine the minimum number of monitoring trails(along with the lightpaths in the routing) required for physicallink failure localization. The third problem is to determine ajoint routing and corresponding failure localization minimizingan objective that is a weighted sum of the objectives of theprevious two problems. In section V a heuristic approach forthe joint routing and failure localization problem is given,along with preliminary computational results.al. [17] considered the problem of augmenting the logicalgraph with additional links to guarantee the existence of asurvivable mapping. An earlier work that discussed augmentation is in [18].B. Physical Link Failure LocalizationThe single-link failure detection in optical-level mechanismhas been studied in [19] and [20]. In [20], the optical failuredetection scheme utilizes monitors. Due to the adoption ofexpensive monitors, the scalability and cost efficiency of thisscheme is not ideal. “Probing” (lightpath) fault diagnosis wereproposed in [21] and [22]. Monitoring trail (m-trial) has beenintroduced in [23], [24] and [25] for localizing link failures.A monitoring trail is a non-simple lightpath that is associatedwith a monitor at a receiver. After identifying a link failure,an alarm would be triggered by a monitor. A control platformwould receive the alarm pattern to uniquely localize the linkfailure detected by a unique combination of m-trails with thealarms. Other related works are in [26] and [27].Failure localization in IP-over-WDM networks can beachieved by adding monitoring equipments in optical networkswhich can monitor the power of optical signals, measure thespectrum of the optical signal, detect transmission disruption,and send out the alarm when a failure is detected [28].Meanwhile, routers in IP networks can also be consideredas monitoring devices which retransmit the packets underfailure [29]. Mas and Thiran [30] studied the properties ofalarms due to failures and proposed an algorithm to locatefailures in the WDM network. The m-trail and m-cycleconcepts rely on the unique combination of pre-determinedlight-trails and cycles to locate the physical link failure, whichconsumes extra wavelengths for monitoring purpose. In thispaper, we would like to consider adding monitors to someuser lightpaths instead of supervisory lightpaths, which wasfirst introduced in [27]. The difference between our approachand the one in [27] is that we consider a layered networkinstead of a single optical network. This design requires anintegrated control plane which is capable of dealing with bothlayers routing information.II. L ITERATURE R EVIEWIn this section, we provide a review of literature on thetopics related to the research in this paper, namely, survivablelogical topology routing in an IP-over-WDM network, andfailure localization in an optical network.A. Survivable Logical Topology RoutingA survivable logical topology mapping can be achievedif the lightpaths in the physical topology corresponding tothis mapping are all link-disjoint. Since finding disjoint pathsbetween pairs of nodes is NP-complete [3], determining asurvivable routing of the logical topology in an IP-overWDM network is also an NP-complete problem. Modiano andNarula-Tam [4] proved a necessary and sufficient condition forsurvivable routing under a single physical link failure in IPover-WDM networks and formulated the problem as an IntegerLinear Program (ILP). Todimala and Ramamurthy [5] adaptedthe concept of Shared Risk Link Group introduced in [6] andalso computed the routing through an ILP formulation. Otherrelated works are in [7][8][9][10].To handle the drawback of ILP approaches Kurant andThiran [11] proposed the Survivable Mapping by Ring Trimming (SMART) framework. Another approach proposed byLee et al. [12] utilized the concept of ear-decomposition onbi-connected topologies. One can show that this is, in fact,a special variant of the framework given in [11], though itwas developed independently. Javed et al. obtained improvedheuristics based on SMART [13] [14]. Using duality theory ingraphs, a generalized theory of logical topology survivabilitywas given by Thulasiraman et al. [15] [16]. Thulasiraman etIII. P ROBLEM D ESCRIPTIONWe let GP (VP , EP ) and GL (VL , EL ) represent thephysical and logical networks, respectively. The relationshipbetween GP and GL is that VL VP . We let e, f, g representphysical edges and u, v represent logical edges. We let i, jdenote physical nodes and s, t the logical nodes. The termsedges and links as well as nodes and vertices will be usedinterchangeably. We assume that both the physical and logicalnetworks are at least two-edge connected.Without loss of generality, we keep the indices of logicalnodes same as their corresponding physical nodes. For alogical edge u we find a path p in the physical topology whosestart and end nodes are the two corresponding nodes of u. Wecall pu the lightpath of u.We let i(u) and j(u) be the physical nodes of logical edgeu and s(e) and t(e) be the logical nodes of physical edge83
V International Workshop on Reliable Networks Design and Modeling (RNDM 2013) co-located with ICUMT 2013e. If u connects s(u) and t(u), then, (s(u), t(u)) u. Thelightpath provides the routing for a logical edge. The failureof any physical edge in pu disconnects the lightpath of u andits corresponding logical edge.In contrast to survivable routing, we define optimum logicaltopology routing in an IP-over-WDM network as follows.Definition 1: A logical topology routing is an optimumrouting in a given IP-over-WDM network, if lightpath routingsfor all logical links in the logical network maintain theconnectivity of the logical network for the largest number ofsingle physical link failures. In other words, under an optimumrouting, the logical network is protected for the largest numberof physical link failures. We denote an optimum routing in agiven IP-over-WDM network as P , where P {p (s, t) :(s, t) EL }.Definition 2: Given a logical topology routing, we defineOLp , the set of physical links each of whose failure disconnects at least one logical cutset, as OLp {(i, j) : CS(S, VL \S), s.t. (i, j) p (s, t) and (s, t) CS(S, VL \S), S VL }.Proposition 1: If a given IP-over-WDM network is survivable, then the optimum routing P is a survivable routing andthe corresponding OL .In this paper we we study three optimizations and developtheir ILP formulations. Specifically, the first problem is todetermine an optimum logical topology routing. Given anoptimum logical topology routing and a set of monitoringtrails, the second problem is to determine the minimumnumber of monitoring trails (along with the lightpaths in therouting) required for physical link failure location. The thirdproblem is to determine a joint routing and correspondingfailure localization minimizing an objective that is a weightedsum of the objectives of the previous two problems.If a given IP-over-WDM network is unsurvivable, insteadof augmenting the logical network to guarantee a survivablerouting, we invoke, after the generation of a optimum P , theexisting monitoring trails in the optical network coupled withlightpath routings P to localize failures of the physical linksin OL.Now, we demonstrate all above definitions in the followingexamples.Example 1: We demonstrate the concept of optimum routing for a given un-survivable IP-over-WDM network inFigs. 1 and 2. In Figure 1, the routings for all logicaledges are P 1 {p112 , p114 , p125 , p145 } with p112 {(1, 2)},p114 {(1, 2), (2, 3), (3, 4)}, p125 {(2, 5)}, and p154 {(4, 5)}. In Figure 2, the routings for all logical edges areP 2 {p212 , p214 , p225 , p224 } with p212 {(1, 2)}, p214 {(1, 6), (6, 5), (5, 4)}, p225 {(2, 5)}, and p245 {(4, 5)}.After the failure of (1, 2), the logical network in Figure 1is disconnected, and after other failures the logical networkin Figure 1 remains connected. So, OLp1 {(1, 2)}. After(4, 5) fails, the logical network in Figure 2 is disconnected,i.e. OLp2 {(4, 5)}. Both P 1 and P 2 are optimum routingsfor the given IP-over-WDM network.Example 2: Based on the optimum routing solutions P 11415654The example of optimum routing for IP-over-WDM network: P 1Fig. 1.141223WDMIPFig. 2.3WDMIP225654The example of optimum routing for IP-over-WDM network: P 2and P 2 , we build the link-path/trail matrix in Table I andTable II. It is obvious that both P 1 and P 2 provide the uniquecombination to identify OLp1 and OLp2 . For P 1 , p112 and p114identify (1, 2). For P 2 , p214 and p245 identify (4, 5). Note herethat {(1, 2), (1, 4)} and {(1, 4), (4, 5)}, respectively, are thetwo cutsets in the given logical network disconnected underthe routings P 1 and P 2 .p114p125p145100100100010001000000TABLE IT HE OPTIMUM LINK - PATH / TRAIL MATRIX FOR F IGURE 4p225p245000000000010101100100TABLE IIT HE OPTIMUM LINK - PATH / TRAIL MATRIX FOR F IGURE ervation 1: Based on Example 1, there exists multiplesolutions for the optimum routing problem in a given IP-overWDM network.Observation 2: Based on Example 2, the lightpaths alonecould identify the failure of OL.Example 3: We now demonstrate the need for monitoringtrails for failure localization. Consider the IP-over-WDMnetwork in Fig. 3, the routing P {p 13 , p 14 , p 36 , p 46 }with p 13 {(1, 2), (2, 3)}, p 14 {(1, 2), (2, 3), (3, 4)},p 36 {(3, 4), (4, 5), (5, 6)}, and p 46 {(4, 5), (5, 6)}is an optimum routing. The corresponding OLp {(1, 2), (2, 3), (4, 5), (5, 6)}. Let MP {m 1 } with monitoring trail m 1 {(1, 2), (2, 5), (5, 6), (6, 1)}. The link-path/trailmatrix is in Table 3. The combination of P and MP providesthe unique combination required to identify each link in OL84
V International Workshop on Reliable Networks Design and Modeling (RNDM 2013) co-located with ICUMT 2013311β: binary indicator. If physical link (i, j) failure disconηijββnects logical cutset β, ηij 1; otherwise, ηij 0.3WDMIP42665A. ILP Formulation for Optimum Logical Topology RoutingWe first discuss the ILP formulation for the optimum routingproblem in a given IP-over-WDM network.To generate the optimum routing in the given IP-overWDM network, flow conservation constraints still hold andare formulatedas follows.XXststyij yji 1,if i s, (s, t) EL (1)4Fig. 3. The example of optimum routing for IP-over-WDM network: Solution2based on row information in Table 3. Row vectors in the linkpath/trail matrix for physical links (1, 2) and (2, 3), and for(4, 5) and (5, 6) are the same. m-trails are necessary to identifythem. The reason to select m-trail m 1 is that a monitoringtrail which routes through (1, 2) and (5, 6), but does not routethrough (2, 3) and (4, 5), could identify (1, 2) and (2, 3), (4, 5)and (5, 6).(i,j) EPX XXstyji 1, if i t, (s, t) EL (2)(i,j) EP(i,j) EPstyij (i,j) EPXstyji 0, otherwise, (s, t) EL . (3)(i,j) EPProposition 2: Given the routing information, (4) and (5)identify OL.Xstyij ( CS(S, VL \ S) 1) zij ,p 46p 36p 14m 11001100011000001011001110001TABLE IIIT HE OPTIMUM LINK - PATH / TRAIL MATRIX FOR F IGURE 3(1,2)(2,3)(3,4)(2,5)(4,5)(5,6)(1,6)(i,j) EPstyijp 131100000(s,t) CS(S,VL \S)(i, j) EP , S VLXstyij(4) CS(S, VL \ S) zij ,(s,t) CS(S,VL \S)(i, j) EP , S VL . (5)Proof: We consider two cases and show that (i, j) is inOL if and only if zij 1.(1) If physical link (i, j) disconnects cutset CS(S, VL \S),the cutset are disconnected, i.e.,P then, all links inst(s,t) CS(S,VL \S) yij CS(S, VL \ S) 0. Hence, byequation (4) zij 1 and (i, j) is in OL.(2) If (i, j) fails, the number of logical links whose lightpathareP disrupted is lessstthan the cardinality of cutset, i.e.,(s,t) CS(S,VL \S) yij CS(S, VL \ S) . Hence, byequation (5) zij 0 and (i, j) is not in OL.IV. O PTIMUM ROUTING , FAILURE L OCALIZATION , ANDILP F ORMULATIONIn this section, we develop integer linear programming (ILP)formulations, which provide an exact solution approach foroptimum routing generation and optimum routing generationwith physical link failure localization. Note here that welet term route m represent routes in the physical network,such as m-trails and lightpaths. We assume that a set of mtrails is given and each node in the network can convert thewavelengths. If m MP, then m stands for an m-trail. Ifm P , then, m stands for a lightpath.M : parameter. A big number.ijfm: parameter. If a route m routes through physical link (i, j),ijij 0.fm 1; otherwise, fmββξst : parameter. If (s, t) is in cutset β, if yes, ξst 1;βotherwise, ξst 0.styij: binary indicator. If lightpath of (s, t) routes throughststphysical link (i, j), yij 1; otherwise, yij 0.zij : binary indicator. If with optimum routing in the givenIP-over-WDM network, (i, j) OL, zij 1; otherwise,zij 0.λm : binary indicator. If a route m MP P is selected,λm 1; otherwise, λm 0.αβ : binary indicator. If cutset β is selected for failure localization or not, if yes. αβ 1; otherwise, αβ 0.cij : the alarm code for physical link (i, j)cβij : partial alarm code for physical link (i, j) with respectto cutset βhuvij : binary indicator, whether cij is greater than cuvhβuv: binary indicator, whether cβij is greater than cβuvijILP for Optimum Routing:Xminzij ,(6)(i,j) EPsubject to:(1) to (5)The above ILP achieves a logical topology routing underwhich the number of physical links each of whose failuredisconnects GL is minimum.B. Logical Topology Routing and Physical Links Failure LocalizationGiven an optimum routing, in this section we develop an ILPformulation to minimize the number of m-trails (besides thelightpaths in the optimum routing) to be selected for physicallink failure localization. Recall that, given a logical topologyrouting, OL is the set of physical links each of whose failuredisconnects the logical topology. For failure localization weneed to localize the failures of only those physical links inOL because the failures of other physical links would notdisconnect the logical topology.85
V International Workshop on Reliable Networks Design and Modeling (RNDM 2013) co-located with ICUMT 2013Suppose we are given a set MP of monitoring trails and aset P of lightpaths used in the logical topology routing. LetLR be the physical link-routing matrix which has one rowfor eachS physical link and one column for each path/trail inMP P and has one in position (k, ) whenever link k isin path/trail . To localize the links in OL we have to select asubset SMP of m-trails in MP such that, for any two physicallinks, theScorresponding rows in the submatrix formed by OLand P SMP are distinct.In the following when we say that a logical cutset identifies(localizes) (i, j) we mean that the set of lightpaths mappingthe logical links in this cutset are selected for localization ofa failure of (i, j). The following proposition contains a keyidea for failure localization.Proposition 3: Given a routing and the corresponding setP of lightpaths. Suppose, under this routing, a logical cutsetCS(S, VL \S) is disconnected when a physical link fails. Then(1) If F(CS(S, VL \ S)) 1, then, (i, j) F(CS(S, VL \S)) failure is identified by cutset CS(S, VL \ S). Inother words, in this case no monitoring trail needs tobe included for identifying (i, j). NOTE: Recall thatF(CS(S, VL \ S)) is the set of physical links each ofwhose failure disconnects the cutset CS(S, VL \ S).(2) If F(CS(S, VL \ S)) 2, then at most F(CS(S, VL \S)) 1 m-trails, in addition to the cutset, are needed toto identify (i, j).With a given optimum routing P , we let SCS be a subsetof logical cutsets which is disrupted by physical link failures.We let β be the index of a cutset.Proposition 4: Suppose SCS be a subset of cutsets suchthat all these cutsets are disconnected because of the failureof one or more physical links. Then(1) If {β SCS } F(β) 1, then the only link causingthe failure of all the cutsets in SCS can be identifiedby {β SCS } β.(2) If {β SCS } F(β) 2, the links each of whose failurecauses the failures of all the cutsets in SCS can beidentified by {β SCS } β and possibly a maximum of {β SCS }F (β ) 1 m-trails.If, for the scenario in (2) in proposition 4, the m-trails arenot availableto generate the combinations of paths/trails inSMP P , then additional m-trails need to be introduced.Now we proceed to generate the different constraints in ourILP formulation to determine an optimum logical topologyrouting along with the unique combinations of lightpaths/mtrails for localization of faults in physical links in OL. Firstwe modify constraints (4) and (5) to provide the connectionbetween physical link (i, j) and a cutset.Xβst yij ( β 1) ηij, β CS, (i, j) OL (7)topology. Constraints (9) and (10) guarantee that αβ 1 ifβ 1 (that is ifand only if for some physical link (i, j), ηijand only if (i, j) failure disconnects cutset β.)Xβαβ ηij,β CS(9)(i,j) EPX(i, j) EP , β CSCode Assignment for Failure LocalizationTo localize the failure in a physical link (i, j) we associatewith (i, j) a combination of lightpaths and m-trails. Thiscombination is captured by a code cij which is basically theinteger value derived from the combination that is given bythe link-path/trail matrix. Since, each cutset β disconnectedby the failure of (i, j) is to be included in the combinationwe exclude the links of β in calculating the value of the code.This partial code will be denoted by cβij . So, we haveXijji βcβij 2m (fm fm)γijm(11)m MP (P \{p st :(s,t) β})βγijm is a binary variable used, whereto select/deselect trailm for each (i, j) cutting of the same β.Constraint (12) ensures that the code is assigned to onlythose physical links in F(β) that satisfies F(β) greater thanor equal to 2. Constraint (13) is to guarantee that an m-trailis chosen to localize (i, j) only when cutset β is selected forlocalization. Constraint (14) is to ensure that cβij is nonzeroonly when cutset β is selected for localization. Constraint (15)says that an m-trail is included in the set of paths/trails forlocalization only if for some cut set β and some physical linkβ(i, j), γijmis nonzero.Finally, the two constraints (16) and (17) guarantee that thepartial codes for two distinct links are different.Given an optimum logical topology routing P , we havethe following mathematical programming formulation thatminimizes the number of monitors required to localize thefailures of the Xlinks in OL.minλmm MPs.t. (7) to (11)Xβcβij M (ηuvαβ 1),β CS, (i, j) OL.(12)(u,v) EPβγijm αβ ,(13)βcβij M αβ ηijβγijm λm ,βcij cβuv 1 M hβuvijββcuv cij 1 M (1 hβuvij )ββuvβijηij , αβ , fm , hij , λm , γijm {0, 1}, cβij(14)β CS, m MP, (i, j) OLβst yij β ηij,(10)β CS(s,t) βXββ,αβ ηijηij(15)(16)(17) 1,(18)Once the codes cβij are obtained then the codes cij can beobtained by simply adding the value corresponding to the links(or corresponding lightpaths) in the cutset β. Note that in theabove formulation (12) is a nonlinear constraint, which can be(8)(s,t) ββConstraints (7) and (8) ensure that ηij 1 if and only if thefailure of physical link (i, j) disconnects cutset β in the logical86
V International Workshop on Reliable Networks Design and Modeling (RNDM 2013) co-located with ICUMT 2013βlinearized with an auxiliary variables ξuv:ββξuv ηuv ,(u, v) OL, β CSβξuvβξuv αβ ,(u, v) OL, β 9)(20)βηuv αβ 1,(u, v) OL, β CS(21)βConstraints (19)-(21) guarantee that the value of ξuv equals toβββηuvαβ . Constraints (19) and (20) force ξuv 0 when ηuv 0βor αβ 0. Constraint (21) allows ηuv 1 if and only if bothβηuv 1 and αβ s32647Surv. %90.1293.5891.9994.9896.53TABLE IVS IMULATION RESULTSMP C , which connect Sβi and Sβj , i 6 j. Once the candidatem-trails are generated, step 13 iterates through all MP Cand finds the minimal number of m-trails whose combinationIn section IV-A we provided an ILP formulation to generatecan be used to identify (i, j) failures. Here we only providean optimum routing that minimizes the number of physicalAlgorithm 1 Survivable routing and failure localization withlinks each of whose failure disconnects the logical topology.minimum m-trailsIn section IV-B, given an optimum routing we provided anRequire: GP (VP , EP ), GL (VL , EL ), MP C ILP formulation to minimize the number of m-trails needed , CS to localize physical link failures. In this section we provide an1: Generate optimum routing P for all logical linksintegrated approach to optimize a weighted sum of the bothij, m P 2: Identify all fmthe objectives of the problems considered in sections IV-A and3: Identify all CS [31]IV-B. This integrated formulation is as follows, where θ and4: for all (i, j) EP doϑ are given weights.ijXX) β, β CS then5:if ( m MP P fmβmin θzij ϑλm6:Sβ Sβ (i, j) {i.e., ηij 1}m MP(i,j) EP7:end ifs.t. Constraints (1) (3), (9) (11), (13) (17), (19) (21) 8: end forXβst9: for (i, j) Sβ1 , (k, ) Sβ2 , where Sβ1 , Sβ2 yij ( β 1) ηij, β CS, (i, j) EP (22)Sβ and Sβ1 6 Sβ2 do(s,t) βX10:Find a path m connecting (i, j) and (k, )βstyij β ηij,β CS, (i, j) EP . (23) 11: MP MP m CC(s,t) β12: end forX βzij ηij ,(i, j) EP(24) 13: Find the minimal cardinality subset of MP C whichuniquely distinguish all (i, j) Sβi , Sβi SββX βM zij ηij ,(i, j) EP(25) the preliminary simulation results for our heuristic due topage limitation. The physical topologies selected are NSF,ββββstβNobel-Germany, Norway, Europe, and COST 266 [32]. Theyij, zij , ηij, ξuv, hβuv,λ,γ {0,1},c 1,m ijmijijcorresponding logical topologies are randomly generated with(i, j) OL, β CS, m MP(26)50% of nodes in the physical topologies and at least twoedge connected. After generating the optimum routing, weV. H EURISTIC A PPROACH AND S IMULATION R ESULTSWe present a heuristic for optimum routing and correspond- apply the heuristic and calculate the number of physical linking failure localization of physical links in two stages. First failures which disconnect the logical topology (denoted asthe optimum routing P for all logical links is generated cuts in Table IV.) For all cuts, additional monitoring trailsusing the concept of protection spanning tree, which was are randomly generated (denoted as m-trails in Table IV.)introduced in [8]. The simulation results in [8] showed that the For optimum routing which is survivable, we also record thegenerated routing cannot guarantee survivability but a routing percentage of survivability (denoted as Surv% in Table IV.)with high probability of survivability can be achieved. Hence The simulation results show that the hybrid approach not onlythe objective of the heuristic introduced below is two-fold: guarantees high percentage of survivable route generation,find a survivable routing when possible; otherwise, provide a but also provides the minimum number of additional m-trailsmechanism to uniquely identify the physical link failure using required in order to uniquely identify all physical link failures.C. Optimum Logical Topology Routing and Minimizing theNumber of m-Trails for Failure Localizationlightpaths and minimum number of m-trails.Step 2 in Algorithm 1 finds the physical link utilization forall lightpaths. For each physical link, step 3 identifies a logicallink set β, β CS, whose failure disconnects the logicaltopology. Steps 4 – 8 group the physical links whose failurecut off the same set of logical links. Those groups are denoteda
to determine an optimum routing and the corresponding failure localization. We also propose a heuristic approach for these problems to handle large scale IP-over-WDM networks. Index Terms—Optical communication, IP-over-WDM network, optimal routing, failure localization, graph theory. I. INTRODUCTION IP-over-WDM network is a two-layered .
