OSA's Digital Library

Optics Express

Optics Express

  • Editor: C. Martijn de Sterke
  • Vol. 19, Iss. 26 — Dec. 12, 2011
  • pp: B882–B894
« Show journal navigation

Impact of electrical grooming and regeneration of wavelength paths in creating hierarchical optical path networks

Hai-Chau Le, Hiroshi Hasegawa, and Ken-ichi Sato  »View Author Affiliations


Optics Express, Vol. 19, Issue 26, pp. B882-B894 (2011)
http://dx.doi.org/10.1364/OE.19.00B882


View Full Text Article

Acrobat PDF (1597 KB)





Browse Journals / Lookup Meetings

Browse by Journal and Year


   


Lookup Conference Papers

Close Browse Journals / Lookup Meetings

Article Tools

Share
Citations

Abstract

We assess the impact of utilizing electrical cross-connects for the intermediate grooming and 3R regeneration of wavelength paths in a hybrid hierarchical optical path network. Simulation results prove that they offer a significant cost reduction. We also investigate the dependencies of network cost on network parameters including optically-transparent reach, electrical switch port cost, and waveband capacity. It is demonstrated that it is critical to choose the waveband capacity properly in order to minimize total network cost.

© 2011 OSA

1. Introduction

An attractive approach to cost-effectively enhancing optical switch capacity is the development of hierarchical optical path networks that employ hierarchical optical cross-connects (HOXCs). HOXCs are capable of switching optical signals at different granularities: wavelengths and wavebands (bundles of wavelengths) [2

2. K. Sato and H. Hasegawa, “Prospects and challenges of multi-layer optical networks,” IEICE Trans. Commun E90-B, 1890–1902 (2007).

5

5. P. Torab, V. Hutcheon, D. Walters, and A. Battou, “Waveband switching efficiency in WDM networks: Analysis and case study,” in Optical Fiber Communication Conference, OSA Technical Digest (CD) (Optical Society of America, 2006), paper OtuG3.

]. Their efficiency, indicated by the cost and port count reductions achieved by hierarchical optical path networks, has been verified [6

6. M. Lee, J. Yu, Y. Kim, C. Kang, and J. Park, “Design of hierarchical cross-connect WDM networks employing a two-stage multiplexing scheme of waveband and wavelength,” IEEE J. Sel. Areas Comm. 20(1), 166–171 (2002). [CrossRef]

9

9. I. Yagyu, H. Hasegawa, and K. Sato, “An efficient hierarchical optical path network design algorithm based on a traffic demand expression in a Cartesian product space,” IEEE J. Sel. Areas Comm. 26(6), 22–31 (2008). [CrossRef]

]. In works [6

6. M. Lee, J. Yu, Y. Kim, C. Kang, and J. Park, “Design of hierarchical cross-connect WDM networks employing a two-stage multiplexing scheme of waveband and wavelength,” IEEE J. Sel. Areas Comm. 20(1), 166–171 (2002). [CrossRef]

, 7

7. M. Li, W. Yao, and B. Ramamurthy, “Same-destination-intermediate grouping vs. end-to-end grouping for waveband switching in WDM mesh networks,” in Proceedings of IEEE International Conference on Communications (Institute of Electrical and Electronics Engineers, 2005), 1807–1812.

], authors investigated the efficiency of waveband switching networks compared to wavelength-routed networks, and demonstrated that their effectiveness depends on the network and traffic conditions. Cost evaluations of hierarchical optical path networks in terms of optical switch port and fiber requirements are given in [8

8. X. Cao, V. Anand, Y. Xiong, and C. Qiao, “A study of waveband switching with multilayer multi-granular optical cross-connects,” IEEE J. Sel. Areas Comm. 21(7), 1081–1095 (2003). [CrossRef]

, 9

9. I. Yagyu, H. Hasegawa, and K. Sato, “An efficient hierarchical optical path network design algorithm based on a traffic demand expression in a Cartesian product space,” IEEE J. Sel. Areas Comm. 26(6), 22–31 (2008). [CrossRef]

]. The results demonstrated that the degree of network cost reduction depends on the network design algorithms applied. Reference [10

10. S. Kakehashi, H. Hasegawa, and K. Sato, “Optical cross-connect switch architectures for hierarchical optical path networks,” IEICE Trans. Commun E91-B, 3174–3184 (2008).

] introduced various HOXC architectures for hierarchical optical path networks, and clarified that necessary optical switch scales can be reduced by employing waveband switching.

In HOXC architectures, the optical cross-connect switch scale required for switching waveband paths can be very small [10

10. S. Kakehashi, H. Hasegawa, and K. Sato, “Optical cross-connect switch architectures for hierarchical optical path networks,” IEICE Trans. Commun E91-B, 3174–3184 (2008).

, 11

11. H. C. Le, H. Hasegawa, and K. Sato, “Hierarchical optical path network design algorithm considering waveband add/drop ratio constraint,” IEEE J. Opt. Commun. Netw. 2(10), 872–882 (2010). [CrossRef]

], and that for the wavelength paths cross-connect (WXC) part is dominant. WXC size is determined by waveband add/drop ratio, the ratio of number of added/dropped waveband paths to that of outgoing/incoming waveband paths. Bounding the waveband add/drop ratio is, therefore, the direct way of effectively reducing the WXC portion [10

10. S. Kakehashi, H. Hasegawa, and K. Sato, “Optical cross-connect switch architectures for hierarchical optical path networks,” IEICE Trans. Commun E91-B, 3174–3184 (2008).

, 11

11. H. C. Le, H. Hasegawa, and K. Sato, “Hierarchical optical path network design algorithm considering waveband add/drop ratio constraint,” IEEE J. Opt. Commun. Netw. 2(10), 872–882 (2010). [CrossRef]

]. Research on a network design algorithm that incorporates a waveband add/drop ratio restriction [11

11. H. C. Le, H. Hasegawa, and K. Sato, “Hierarchical optical path network design algorithm considering waveband add/drop ratio constraint,” IEEE J. Opt. Commun. Netw. 2(10), 872–882 (2010). [CrossRef]

] revealed that even if the add/drop ratio is held to a small value, say 0.3, the increase in required network resources such as optical switch ports and fibers can be very small.

Another possible approach to realizing HOXCs with current technologies is utilizing electrical switches for handling wavelength paths. Subsequent works confirmed the effectiveness of hybrid hierarchical optical path networks that incorporate both optical cross-connects for higher order optical paths, waveband paths, and electrical cross-connects (EXCs) for lower order optical paths, wavelength paths [12

12. R. Izmailov, S. Ganguly, T. Wang, Y. Suemura, Y. Maeno, and S. Araki, “Hybrid hierarchical optical networks,” IEEE Commun. Mag. 40(11), 88–94 (2002). [CrossRef]

16

16. H. C. Le, H. Hasegawa, and K. Sato, “Hybrid optical WDM networks utilizing optical waveband and electrical wavelength cross-connects,” in Optical Fiber Communication Conference, OSA Technical Digest (CD) (Optical Society of America, 2011), paper NMC3.

]; the key is suppressing the electrical cross-connect portion. Although transparent optical switches offer various merits in terms of large throughput, bit rate and protocol independence, electrical switches can provide wavelength conversion and 3R regeneration functions. The 3R functions are inevitable when network size is larger than the transparent optical reach, and they can additionally provide wavelength conversion as elaborated below. This can be achieved by exploiting the mature commercial technologies that underlie SDH/SONET and OTN cross-connects. We have already proposed an efficient hybrid-hierarchical optical cross-connect (hybrid-HOXC) architecture [16

16. H. C. Le, H. Hasegawa, and K. Sato, “Hybrid optical WDM networks utilizing optical waveband and electrical wavelength cross-connects,” in Optical Fiber Communication Conference, OSA Technical Digest (CD) (Optical Society of America, 2011), paper NMC3.

] that separates the wavelength adding/dropping and grooming functions at the WXC layer, which significantly reduces switch scale. For intermediate grooming of wavelength paths, therefore, the proposed hybrid-HOXC can utilize small scale EXCs. Due to the necessity of OE/EO converters at the inputs and outputs of the electrical switching matrices, the EXCs can easily provide wavelength conversion and 3R regeneration. Thus, hybrid hierarchical optical path networks can perform 3R regeneration and wavelength conversion in combination with intermediate grooming of wavelength paths at EXCs. This idea will help to enhance the value of the hybrid-HOXCs, particularly when they are applied to large-scale (long reach) networks that require 3R regeneration. This paper highlights this point and clarifies the effectiveness of the hybrid-HOXCs for such optical networks.

The quality of the transmitted optical signals is degraded by noise and signal distortion, i.e. physical impairments; they accumulate along the optical paths and consequently limit the optical transparent transmission reach, the maximum distance that an optical signal can be transmitted without 3R regeneration. The impairment-aware design problem recently has received attention for the routing and wavelength assignment (RWA) of transparent optical networks [17

17. S. Azodolmolky, M. Klinkowski, E. Marin, D. Careglio, J. Pareta, and I. Tomkos, “A survey on physical layer impairments aware routing and wavelength assignment algorithms in optical networks,” Comput. Netw. 53(7), 926–944 (2009). [CrossRef]

21

21. M. Youssef, S. Al Zahr, and M. Gagnaire, “Cross optimization for RWA and regenerator placement in translucent WDM networks,” in Proceedings of Conference on Optical Network Design and Modeling (2010), 1–6.

]. The impairment-aware design problem including RWA and 3R placement problems is known to be NP-complete [17

17. S. Azodolmolky, M. Klinkowski, E. Marin, D. Careglio, J. Pareta, and I. Tomkos, “A survey on physical layer impairments aware routing and wavelength assignment algorithms in optical networks,” Comput. Netw. 53(7), 926–944 (2009). [CrossRef]

]. Thus these studies commonly establish optical paths one-by-one, i.e. they employ the sequential heuristic approach, so as to satisfy the impairment constraints. In hierarchical optical path networks, the difficulty of the design problem is greatly increased since the grooming issue of wavelength paths into waveband paths must be taken into account.

This paper is the first, as far as the authors know, to investigate the impairment-limited design problem in translucent hierarchical optical path networks employing hybrid-HOXCs which combine electrical cross-connects for wavelength path level cross-connection and 3R regeneration with optical waveband cross-connects (BXCs). To design large-scale translucent optical path networks and make full use of the advantages of hybrid-HOXCs, we propose a heuristic algorithm that considers the optical transparent reach limit and encourages the establishment of highly utilized waveband paths by grooming residual sparse wavelength paths while considering electrical port cost. Simulations prove that the hybrid-HOXC based networks designed by the proposed algorithm offer a substantial cost reduction compared to the corresponding single layer optical path network. We also analyze the effectiveness of the hybrid-hierarchical optical path network with respect to the EXC port cost and waveband capacity.

2. Impairment-aware design for hybrid hierarchical optical path network

We assume the hybrid-hierarchical optical cross-connect, shown in Fig. 1
Fig. 1 Hybrid-HOXC architecture.
, that can handle different optical path granularities: wavelength paths and waveband paths. This hybrid-HOXC architecture consists of 2 switching layers; waveband and wavelength path switching layers. The waveband switching layer is realized by an optical waveband cross-connect to route waveband paths. The wavelength switching layer is separated into two functional parts for adding/dropping and grooming operations with wavelength path granularity. This configuration minimizes the required switch scale. The wavelength path adding/dropping operations can be done using supplemental optical devices (i.e. WSSs) or they can be integrated into the switch portions that are required to attain colorless/directionless capabilities, which is the same as in a single layer OXC (not discussed further). An EXC is implemented for grooming wavelength paths. As mentioned before, the EXC can offer wavelength conversion and 3R regeneration. As a result, no separate expensive 3R regenerator is implemented in the hybrid-hierarchical optical path network. Moreover, the EXC may also offer sub-lambda (Virtual Container of ODU) level switching capabilities when it is necessary, however, this is not discussed here for simplicity.

3. Network design algorithm considering the optical transparent reach constraint

3.1 Preliminary

We assume that each fiber can carry up to B wavebands and each waveband consists of W wavelengths. We denote the given physical topology by G(V, A), where V is the set of all nodes and A is the set of all arcs. Matrix C is the set of all traffic demands, where each element, Cs,d, is the number of wavelength paths requested between node pair (s, d). Hereafter, the optical transparent reach limit is represented by the hop count limitation, denoted by K; it is set constant for all optical paths in the network for notational simplicity, however, if it is necessary, the generalization to the variable limit case is straightforward. The design goal is to minimize the total network cost required to accommodate all traffic demands subject to the given optical transparent reach limit.

In the hierarchical optical path network, the cost reduction can be attained by reducing EXC operation along with improving the waveband utilization efficiency by encouraging the use of free wavelengths within already established waveband paths. We need to evaluate the degree of the cost reduction obtained by EXC cut-through operations. Let costλ(u, v) :V2R+, R+ is the set of all nonnegative numbers, be the required port cost of implementing a wavelength path accommodated as a series of sequentially connected 1-hop waveband paths placed on the shortest route between u and v. Here, we assume that one of the shortest paths between source and destination will be assigned to the wavelength path. Similarly, we define costwb(u,v; s,d) :V2×V2R+ as the necessary port cost of routing the wavelength path between u and v as a part of the waveband path that directly connects nodes (s, d). The cost functions of costλ(u, v) and costwb(u,v;s,d) are obtained as follows,

costλ(u,v)=2CEXC(hop(u,v)1)+2W(CBXC_UNI+CBXC_NNI)hop(u,v) andcostwb(u,v;s,d)=2CEXC(hop(u,s)+hop(d,v))+2W{CBXC_UNI(hop(u,s)+hop(d,v)+1)+CBXC_NNI(hop(u,s)+hop(s,d)+hop(d,v))} where hop(u, v) is the minimum hop count between node pair (u, v), CEXC the EXC port cost, and CBXC_UNI and CBXC_NNI are, respectively, the add/drop waveband port cost and the by-pass waveband port cost of the BXC. Based on the port cost functions of costλ(u,v) and costwb(u,v; s,d), we then have the following relative cost reduction obtained by employing waveband switching in the network,

gain(s,d;u,v)=costλ(u,v)costwb(u,v;s,d)costλ(u,v)

3.2 Proposed design algorithm

In order to minimize the total network cost while satisfying the optical reach restriction and fully utilizing the advantages of the hybrid-HOXC nodes, the direct establishment of highly utilized waveband paths that do not exceed K hops is encouraged, whereas grooming operations will be applied only to accommodate the sparse remaining wavelength paths that cannot be efficiently carried by any end-to-end waveband to improve the utilization of waveband paths, since electrical EXC ports are relatively expensive. Our proposed algorithm consists of 2 major steps. The first step is routing and assignment of waveband paths; it searches for and establishes waveband paths that are equal to or shorter than K hops and can be effectively filled up with wavelength paths. The second step is to accommodate all sparse remaining wavelength paths by applying an auxiliary full-mesh virtual wavelength path graph based on established waveband paths with spare capacities or new direct end-to-end unexceeded K hops waveband paths. In both steps, to find the route of waveband/wavelength paths, a proposed un-exceeded K-hops shortest path algorithm is applied (see Appendix). The developed design algorithm is briefly described as follows:

<Hybrid-Hierarchical Optical Path Network Design Considering the Optical Transparent Reach Limit>

  • Step 0- Selection of parameter values

    Determine the following proper values:

    • Xwb: waveband construction threshold, (Xwb (0,1])
    • hlim: incremental hop count limit.
  • Step 1- Routing and Assignment of Waveband Paths with the optical transparent reach limit
  • a) Searching for a highly utilized waveband path
    • Search for node pair (s, d) VxV of a waveband path that satisfies:
      • (1) hop(s, d) = max{ hop(u, v) ≤ K | (u, v) VxV}.
      • (2) maximize the total cost reduction that can be achieved by setting the waveband connecting s and d:

f(s,d)=(u,v)N(s,d)gain(s,d;u,v)>0gain(s,d;u,v)

in which N(s, d) is the set of candidate wavelength paths that can be groomed and carried by a waveband path connecting s and d; N(s, d) satisfies

f(s,d)=(u,v)N(s,d)gain(s,d;u,v)>0gain(s,d;u,v)

and ∀ (u, v)N(s, d): hop(u,s) + hop(s,d) + hop(d,v) ≤ hop(u,v) + hlim .

  • If such a node pair does not exist, go to Step 2. Otherwise, for all (si, di) {(u, v)N(s, d) | gain(s, d; u, v)>0}, assign the traffic demand of node pair (si, di) on to concatenated node pairs (si, s) if si≠s, (s, d) and (d, di) if di≠d.
    • b) Routing and waveband assignment
  • Define an auxiliary multi-layer waveband graph of the network as,

GBand={GbBand=(V,Ab)|1bB}

in which each graph layer GbBand=(V,Ab)is the corresponding network graph for the bth waveband, Bandb (1≤b≤B). Arc set Ab of GbBand is derived from all edges in G with modified arc weight wbBand:V2R+, where arc weightwbBand is based on the number of unoccupied wavebands in established fibers on the arc, denoted by fb (fb ≥0). The weighting function for arc set Ab is defined by,

wbBand(vi,vj)={(1fbε){2CBXC_NNI+Cfiber(vi,vj)B}iffb>0(1+Δ){2CBXC_NNI+Cfiber(vi,vj)B}elseiffb=0,

  • Find the shortest waveband path that does not exceed K hops, rb, on each layer of the auxiliary multi-layer waveband graph GbBand (b = 1,..,B) and then select the shortest route rb0 (b0 is the waveband index) from among the found waveband routes:

    rb0 = min{ rb| 1 ≤ b ≤ B}.

  • Establish the corresponding end-to-end waveband path from s to d on the route rb0 and assign waveband index b0 to carry the total traffic demand sum(s, d) required in Step 1.a.
    • c) Repeat Step 1 until no such waveband path remains.
    • Step 2- Grooming Sparse Remaining Wavelength Paths
    • a)Construct an auxiliary full-mesh virtual wavelength path graph Gλ = (V, Aλ)

      Auxiliary full-mesh virtual wavelength graph Gλ is based on established waveband paths with spare capacities or new direct end-to-end waveband paths that do not exceed K hops.

  • Arc weight wλ of Gλ, where wλ:V2R+, is given by

wλ(vi,vj)=min{Cexistedwb(vi,vj),Ce2ewb(vi,vj)},

where Ce2e-wb(vj, vj) is the minimum cost of routing a wavelength by employing a new end-to-end un-exceeded-K-hop waveband path directly connecting vi and vj (if no end-to-end un-exceeded-K-hop waveband path between vi and vj is available, Ce2e-wb(vj, vj) is set to infinity), and Cexisted wb(vj, vj), the cost of using an established waveband path with free capacity between vi and vj, is given by

Cexistedwb(vi,vj)={2CEXCifthereexistsanestablishedwavebandwithfreewavelength(s)otherwise,

  • b) Routing and wavelength assignment of each remaining wavelength path
    • For each remaining wavelength path request, in descending order of the hop count between its source and destination, apply Dijkstra’s algorithm to find the shortest path based on the virtual wavelength path graph and then, assign the request to the shortest path thus found.
    • Update graph Gλ and repeat Step 2.b until all requested traffic demands are satisfied.

4. Numerical experiments

We adopt the following parameters for the numerical simulations:

  • Physical network topologies: 5x5 regular mesh network and pan-European network (COST266) consisting of 26 nodes and 51 links [22

    22. R. Inkret, A. Kuchar, and B. Mikac, “Advanced infrastructure for photonic networks,” (2008). http://www.ure.cas.cz/dpt240/cost266/docs/COST266_extended_final_report.pdf

    ] (shown in Fig. 3
    Fig. 3 Experimental network topologies.
    ).
    Fig. 3Experimental network topologies.
  • Uniformly and randomly distributed traffic demand is represented as the average number of wavelength paths requested between each node pair.
  • Capacity of fiber: BxW wavelengths per fiber; each fiber carries B wavebands and each waveband accommodates W wavelengths.
  • No waveband conversion.
  • Parameter β is defined as the ratio of the cost of an electrical switch port (including OE/EO) to that of an optical switch port (β = CEXC/CBXC_NNI).
  • Parameter K stands for the optical transparent reach limit of waveband/wavelength paths.

We applied the proposed algorithm with all possible threshold values Xwb{1/W, 2/W, …, W/W}; the threshold value that minimizes the total network cost is then selected. The obtained network costs are normalized by that of the comparable single-layer optical path network utilizing OXCs with the same restriction on optical transparent reach. The network costs are evaluated with 10 different traffic patterns for every traffic demand and each threshold Xwb; their ensemble averages were then plotted.

4.1 Network cost evaluation results

Figure 4
Fig. 4 Network cost evaluation for 5x5 network.
shows the network cost comparison for the 5x5 regular mesh network with the optical transparent reach K of 3 and the EXC port cost ratio β of 3. The results indicate that the translucent hierarchical optical path network offers lower cost than the corresponding single-layer optical path network (normalized cost is less than 1). The cost reduction can reach 50% and strengthens as the traffic demand increases for all applied algorithms. Moreover, the graphs also show that our proposed algorithm outperforms other conventional algorithms (TDEC3R and End-to-End3R) and always offers the best cost reduction for all traffic demand values.

Figure 5
Fig. 5 Network cost comparison for COST266 network.
illustrates the normalized network costs yielded by the proposed algorithm, TDEC3R and OBXC3R algorithms for the COST266 network with following parameter values; B=W=8; the optical transparent reach K=2 and β=1. The graphs also show that the cost reduction of the translucent hierarchical optical path network increases as the traffic demand increases, and can reach 60%. In this network topology, except for the very small traffic area (i.e. less than 0.4), the proposed algorithm offers the lowest cost.

4.2 Impact of network parameters

In this part, we investigate the dependencies of the total network cost on important network parameters such as optical transparent reach, EXC port cost and waveband capacity for the COST266 network. Fiber capacity is 8 wavebands (B=8) and each waveband consists of 8 wavelengths (W=8).

a) Optical transparent reach

b) EXC port cost

c) Waveband capacity

The theoretical analysis in [9

9. I. Yagyu, H. Hasegawa, and K. Sato, “An efficient hierarchical optical path network design algorithm based on a traffic demand expression in a Cartesian product space,” IEEE J. Sel. Areas Comm. 26(6), 22–31 (2008). [CrossRef]

] of the impact of waveband capacity W on the total port count, which mainly determines the total network cost of a hierarchical optical path network, proved that the hierarchical optical path network offers greater cost reduction with larger W when traffic demands are not small. In this part, we fix the fiber capacity in terms of wavelength number as a constant (BxW=64) and the waveband capacity, W, was varied (2, 4, 8, 16 and 32). The normalized COST 266 network costs with β=2 and K=3 with respect to different waveband capacity values (W=2, 4, 8, 16 and 32), where the average traffic demand between node pairs is changed, are shown in Fig. 8
Fig. 8 Impact of waveband capacity.
.

It is shown that, depending on the traffic demand, the proper waveband capacity must be selected to minimize network cost. For the traffic demands of 2 and 4, the optimal waveband capacity value is 8 while the waveband capacity of 16 is the best for larger traffic demand (traffic demand of 8). Because of the fixed fiber capacity, selecting a smaller waveband capacity can help improve the waveband utilization efficiency but at the cost of increasing the number of waveband paths (and hence waveband ports) necessary as well as the number of expensive EXC ports required for grooming operations to carry the same given traffic demand, and as a result, the total network cost is increased. On the other hand, large waveband capacity such as 32 reduces the network cost less significantly. Even though the waveband utilization efficiency is weakened, since the given traffic demands are not great enough to occupy the huge waveband paths.

5. Conclusions

The value of the hybrid-HOXC can be significant when it is applied to large-scale networks that require 3R regeneration. Translucent hierarchical optical path networks implementing hybrid-HOXCs can incorporate 3R regeneration in waveband grooming operations; it is processed simultaneously at the EXCs of intermediate nodes. In order to minimize the total network cost under the physical impairment constraint, we have developed a translucent hierarchical optical path network design algorithm that considers the optical transparent reach constraint. Simulations proved that substantial cost reductions can be achieved by implementing the proposed hybrid network. The proposed algorithm is especially effective for large networks and large traffic demands, and strongly depends on the cost of EXC ports. We also investigated the dependence of the network cost on the optical transparent reach and the selection of waveband capacity. It was demonstrated that it is critical to choose the waveband capacity properly to minimize total network cost.

Appendix

We propose a dynamic programming algorithm that can find the shortest path whose hop count does not exceed a given threshold, K, in a non-negative graph. The algorithm is briefly described as follows:

Input

  • Given non-negative graph G(V, A) where V={v1, …, vN } is the set of vertices and A={(vi, vj) | a(vi, vj) ≥0} is the set of arcs in which a(vi, vj) is the weight of the arc between node vi and node vj; a(vi, vj) = ∞ if there is no physical connection between node vi and node vj.
  • Source and destination node pair: (s, d) VxV
  • Hop count limit: K

Output

  • r(s, d) = the shortest route from s to d that is less than K hops
  • DK(s, d) = Minimum value of the shortest path from s to d

Variables

  • d[k][v] = minimum cost of the k-hop shortest path connecting node pair (s,v) in which v V; and k is the hop count of the route (k {1,.., K}).
  • prev[k][v] = the preceding node of v on the shortest route from the source s to v that has exactly k hops.
  • Selected[v] = Selection status of node v (= 1 iff v was selected; = 0 if not)

The proposed algorithm:

  • 1. Initialization (k=1)
    • d [1][v]: = a(s,v) v ≠ s
    • prev [1][v]: = s v ≠ s
    • d[i][v]: = ∞ v; i = 2,..,K
  • 2. While (k<K) do
    • a) Clear the selection status of all nodes

      Selected[t]: = 0 t V; t≠ s

      Selected[s]: = 1

    • b) Find node i that satisfies:

      d[k][i] = min{d[k][t] | tV; Selected[t]=0}

    • c) If found i
      • (1) Relabel all nodes

        For tV

        If (d[k+1][t] > d[k][i] + a[i, t])

        Begin

        d[k+1][t]: = d[k][i] + a[i, t]

        prev[k+1][t]:= i

        End

      • (2) Selected[i]: = 1 and Go back to b).

        d) k: = k + 1;

End while

  • 3. The minimum cost and the route
    • DK(s, d) = min{ d[k][d] | 1≤ kK}
    • If the un-exceeded-K-hop shortest route is available (DK(s, d) < ∞), route r(s, d) can be obtained from prev[k][v].

Acknowledgment

This work was partly supported by Japan NEDO Green IT Project and JSPS KAKENHI (23246072).

References and links

1.

K.-I. Sato, Advances in Transport Network Technologies - Photonic Networks, ATM and SDH- (Artech House, 1996).

2.

K. Sato and H. Hasegawa, “Prospects and challenges of multi-layer optical networks,” IEICE Trans. Commun E90-B, 1890–1902 (2007).

3.

X. Cao, V. Anand, and C. Qiao, “Framework for waveband switching in multigranular optical networks: part I- Multigranular cross-connect architectures,” J. Opt. Netw. 5(12), 1043–1055 (2006). [CrossRef]

4.

K. Sato and H. Hasegawa, “Optical networking technologies that will create future bandwidth abundant networks,” IEEE J. Opt. Commun. Netw. 1(2), A81–A93 (2009). [CrossRef]

5.

P. Torab, V. Hutcheon, D. Walters, and A. Battou, “Waveband switching efficiency in WDM networks: Analysis and case study,” in Optical Fiber Communication Conference, OSA Technical Digest (CD) (Optical Society of America, 2006), paper OtuG3.

6.

M. Lee, J. Yu, Y. Kim, C. Kang, and J. Park, “Design of hierarchical cross-connect WDM networks employing a two-stage multiplexing scheme of waveband and wavelength,” IEEE J. Sel. Areas Comm. 20(1), 166–171 (2002). [CrossRef]

7.

M. Li, W. Yao, and B. Ramamurthy, “Same-destination-intermediate grouping vs. end-to-end grouping for waveband switching in WDM mesh networks,” in Proceedings of IEEE International Conference on Communications (Institute of Electrical and Electronics Engineers, 2005), 1807–1812.

8.

X. Cao, V. Anand, Y. Xiong, and C. Qiao, “A study of waveband switching with multilayer multi-granular optical cross-connects,” IEEE J. Sel. Areas Comm. 21(7), 1081–1095 (2003). [CrossRef]

9.

I. Yagyu, H. Hasegawa, and K. Sato, “An efficient hierarchical optical path network design algorithm based on a traffic demand expression in a Cartesian product space,” IEEE J. Sel. Areas Comm. 26(6), 22–31 (2008). [CrossRef]

10.

S. Kakehashi, H. Hasegawa, and K. Sato, “Optical cross-connect switch architectures for hierarchical optical path networks,” IEICE Trans. Commun E91-B, 3174–3184 (2008).

11.

H. C. Le, H. Hasegawa, and K. Sato, “Hierarchical optical path network design algorithm considering waveband add/drop ratio constraint,” IEEE J. Opt. Commun. Netw. 2(10), 872–882 (2010). [CrossRef]

12.

R. Izmailov, S. Ganguly, T. Wang, Y. Suemura, Y. Maeno, and S. Araki, “Hybrid hierarchical optical networks,” IEEE Commun. Mag. 40(11), 88–94 (2002). [CrossRef]

13.

R. Izmailov, S. Ganguly, V. Kleptsyn, and A. C. Varsou, “Non-uniform waveband hierarchy in hybrid optical networks,” in Proceedings of 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (Institute of Electrical and Electronics Engineers, 2003), 1344–1354.

14.

S. Yao, C. Ou, and B. Mukherjee, “Design of hybrid optical networks with waveband and electrical TDM switching,” in Proceedings of Global Communications Conference (Institute of Electrical and Electronics Engineers, 2003), 2803–2808.

15.

S. S. Lee, M. C. Yuang, and P. L. Tien, “Impact of waveband switching on dimensioning multi-granular hybrid optical networks,” in Proceedings of Conference on Optical Network Design and Modeling (2005), 371–381.

16.

H. C. Le, H. Hasegawa, and K. Sato, “Hybrid optical WDM networks utilizing optical waveband and electrical wavelength cross-connects,” in Optical Fiber Communication Conference, OSA Technical Digest (CD) (Optical Society of America, 2011), paper NMC3.

17.

S. Azodolmolky, M. Klinkowski, E. Marin, D. Careglio, J. Pareta, and I. Tomkos, “A survey on physical layer impairments aware routing and wavelength assignment algorithms in optical networks,” Comput. Netw. 53(7), 926–944 (2009). [CrossRef]

18.

A. Patel, C. Gao, J. Jue, X. Wang, Q. Zhang, P. Palacharla, and T. Naito, “Traffic grooming and regenerator placement in impairment-aware optical WDM networks,” in Proceedings of Conference on Optical Network Design and Modeling (2010), 72–77.

19.

C. Saradhi and S. Subramaniam, “Physical layer impairment aware routing (PLIAR) in WDM optical networks: Issues and challenges,” Commun. Surveys Tuts. 11(4), 109–130 (2009). [CrossRef]

20.

B. Garcia-Manrubia, P. Pavon-Marino, R. Aparicio-Pardo, M. Klinkowski, and D. Careglio, “Offline impairment-aware RWA and regenerator placement in translucent optical networks,” J. Lightwave Technol. 29(3), 265–277 (2011). [CrossRef]

21.

M. Youssef, S. Al Zahr, and M. Gagnaire, “Cross optimization for RWA and regenerator placement in translucent WDM networks,” in Proceedings of Conference on Optical Network Design and Modeling (2010), 1–6.

22.

R. Inkret, A. Kuchar, and B. Mikac, “Advanced infrastructure for photonic networks,” (2008). http://www.ure.cas.cz/dpt240/cost266/docs/COST266_extended_final_report.pdf

OCIS Codes
(060.4251) Fiber optics and optical communications : Networks, assignment and routing algorithms
(060.4253) Fiber optics and optical communications : Networks, circuit-switched

ToC Category:
Backbone and Core Networks

History
Original Manuscript: September 30, 2011
Revised Manuscript: November 25, 2011
Manuscript Accepted: November 26, 2011
Published: December 8, 2011

Virtual Issues
European Conference on Optical Communication 2011 (2011) Optics Express

Citation
Hai-Chau Le, Hiroshi Hasegawa, and Ken-ichi Sato, "Impact of electrical grooming and regeneration of wavelength paths in creating hierarchical optical path networks," Opt. Express 19, B882-B894 (2011)
http://www.opticsinfobase.org/oe/abstract.cfm?URI=oe-19-26-B882


Sort:  Author  |  Year  |  Journal  |  Reset  

References

  1. K.-I. Sato, Advances in Transport Network Technologies - Photonic Networks, ATM and SDH- (Artech House, 1996).
  2. K. Sato and H. Hasegawa, “Prospects and challenges of multi-layer optical networks,” IEICE Trans. CommunE90-B, 1890–1902 (2007).
  3. X. Cao, V. Anand, and C. Qiao, “Framework for waveband switching in multigranular optical networks: part I- Multigranular cross-connect architectures,” J. Opt. Netw.5(12), 1043–1055 (2006). [CrossRef]
  4. K. Sato and H. Hasegawa, “Optical networking technologies that will create future bandwidth abundant networks,” IEEE J. Opt. Commun. Netw.1(2), A81–A93 (2009). [CrossRef]
  5. P. Torab, V. Hutcheon, D. Walters, and A. Battou, “Waveband switching efficiency in WDM networks: Analysis and case study,” in Optical Fiber Communication Conference, OSA Technical Digest (CD) (Optical Society of America, 2006), paper OtuG3.
  6. M. Lee, J. Yu, Y. Kim, C. Kang, and J. Park, “Design of hierarchical cross-connect WDM networks employing a two-stage multiplexing scheme of waveband and wavelength,” IEEE J. Sel. Areas Comm.20(1), 166–171 (2002). [CrossRef]
  7. M. Li, W. Yao, and B. Ramamurthy, “Same-destination-intermediate grouping vs. end-to-end grouping for waveband switching in WDM mesh networks,” in Proceedings of IEEE International Conference on Communications (Institute of Electrical and Electronics Engineers, 2005), 1807–1812.
  8. X. Cao, V. Anand, Y. Xiong, and C. Qiao, “A study of waveband switching with multilayer multi-granular optical cross-connects,” IEEE J. Sel. Areas Comm.21(7), 1081–1095 (2003). [CrossRef]
  9. I. Yagyu, H. Hasegawa, and K. Sato, “An efficient hierarchical optical path network design algorithm based on a traffic demand expression in a Cartesian product space,” IEEE J. Sel. Areas Comm.26(6), 22–31 (2008). [CrossRef]
  10. S. Kakehashi, H. Hasegawa, and K. Sato, “Optical cross-connect switch architectures for hierarchical optical path networks,” IEICE Trans. CommunE91-B, 3174–3184 (2008).
  11. H. C. Le, H. Hasegawa, and K. Sato, “Hierarchical optical path network design algorithm considering waveband add/drop ratio constraint,” IEEE J. Opt. Commun. Netw.2(10), 872–882 (2010). [CrossRef]
  12. R. Izmailov, S. Ganguly, T. Wang, Y. Suemura, Y. Maeno, and S. Araki, “Hybrid hierarchical optical networks,” IEEE Commun. Mag.40(11), 88–94 (2002). [CrossRef]
  13. R. Izmailov, S. Ganguly, V. Kleptsyn, and A. C. Varsou, “Non-uniform waveband hierarchy in hybrid optical networks,” in Proceedings of 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (Institute of Electrical and Electronics Engineers, 2003), 1344–1354.
  14. S. Yao, C. Ou, and B. Mukherjee, “Design of hybrid optical networks with waveband and electrical TDM switching,” in Proceedings of Global Communications Conference (Institute of Electrical and Electronics Engineers, 2003), 2803–2808.
  15. S. S. Lee, M. C. Yuang, and P. L. Tien, “Impact of waveband switching on dimensioning multi-granular hybrid optical networks,” in Proceedings of Conference on Optical Network Design and Modeling (2005), 371–381.
  16. H. C. Le, H. Hasegawa, and K. Sato, “Hybrid optical WDM networks utilizing optical waveband and electrical wavelength cross-connects,” in Optical Fiber Communication Conference, OSA Technical Digest (CD) (Optical Society of America, 2011), paper NMC3.
  17. S. Azodolmolky, M. Klinkowski, E. Marin, D. Careglio, J. Pareta, and I. Tomkos, “A survey on physical layer impairments aware routing and wavelength assignment algorithms in optical networks,” Comput. Netw.53(7), 926–944 (2009). [CrossRef]
  18. A. Patel, C. Gao, J. Jue, X. Wang, Q. Zhang, P. Palacharla, and T. Naito, “Traffic grooming and regenerator placement in impairment-aware optical WDM networks,” in Proceedings of Conference on Optical Network Design and Modeling (2010), 72–77.
  19. C. Saradhi and S. Subramaniam, “Physical layer impairment aware routing (PLIAR) in WDM optical networks: Issues and challenges,” Commun. Surveys Tuts.11(4), 109–130 (2009). [CrossRef]
  20. B. Garcia-Manrubia, P. Pavon-Marino, R. Aparicio-Pardo, M. Klinkowski, and D. Careglio, “Offline impairment-aware RWA and regenerator placement in translucent optical networks,” J. Lightwave Technol.29(3), 265–277 (2011). [CrossRef]
  21. M. Youssef, S. Al Zahr, and M. Gagnaire, “Cross optimization for RWA and regenerator placement in translucent WDM networks,” in Proceedings of Conference on Optical Network Design and Modeling (2010), 1–6.
  22. R. Inkret, A. Kuchar, and B. Mikac, “Advanced infrastructure for photonic networks,” (2008). http://www.ure.cas.cz/dpt240/cost266/docs/COST266_extended_final_report.pdf

Cited By

Alert me when this paper is cited

OSA is able to provide readers links to articles that cite this paper by participating in CrossRef's Cited-By Linking service. CrossRef includes content from more than 3000 publishers and societies. In addition to listing OSA journal articles that cite this paper, citing articles from other participating publishers will also be listed.


« Previous Article  |  Next Article »

OSA is a member of CrossRef.

CrossCheck Deposited