The Experts below are selected from a list of 6726 Experts worldwide ranked by ideXlab platform
Yoshiaki Tanaka - One of the best experts on this subject based on the ideXlab platform.
-
A Logical Topology Design with Tabu Search in IP over WDM Optical Networks
2006 Asia-Pacific Conference on Communications, 2006Co-Authors: Sugang Xu, Yoshiaki TanakaAbstract:Given a static traffic condition, the motivation of Logical Topology design in IP over WDM networks is to optimize the network resource utilization and improve network performance. The objectives of the optimization can be to minimize network congestion or to reduce packet delay in the networks. The Logical Topology design for IP over WDM networks can be decomposed into several subproblems, some of those subproblems have been proven to be NP-hard problems, and many heuristic algorithms have been proposed to find the near optimal solutions. Our research effort has been put into the investigation of different heuristic algorithms for the Logical Topology design problem. Using an indirect neighbour discovery method to change the Logical Topology of the network, several simulated annealing and genetic algorithms for Logical topologic design problem in WDM networks have been proposed in our previous researches. In this paper, a tabu search (TS) method to resolve the Logical Topology design problem is proposed. Our motivation is to find a feasible meta-heuristic algorithm for Logical Topology design in IP over WDM networks.
-
a two stage simulated annealing Logical Topology reconfiguration in ip over wdm networks
IEICE Transactions on Communications, 2005Co-Authors: Kaoru Sezaki, Yoshiaki TanakaAbstract:WDM optical networks represent the future direction of high capacity wide-area network applications. By creating optical paths between several nodes in the core networks, a Logical Topology can be created over the physical Topology. By reconfiguring the Logical Topology, network resource utilization can be optimized corresponding to traffic pattern changes. From the viewpoint of network operation, the complexity of reconfiguration should be minimized as well. In this paper we consider the Logical Topology reconfiguration in arbitrary Topology IP over WDM networks with balancing between network performance and operation complexity. The exact formulation of the Logical Topology reconfiguration problem is usually represented as Mixed Integer Linear Programming, but it grows intractable with increasing network size. Here we propose a simulated annealing approach in order to both determine the target Topology with a smaller Logical Topology change and also satisfy the performance requirement. A threshold on the congestion performance requirement is used to balance the optimal congestion requirement and operation complexity. This is achieved by tuning this threshold to a feasible value. For effective solution discovery, a two-stage SA algorithm is developed for multiple objectives optimization.
-
a two stage simulated annealing Logical Topology reconfiguration in ip over wdm networks
International Telecommunications Network Strategy and Planning Symposium, 2004Co-Authors: Kaoru Sezaki, Yoshiaki TanakaAbstract:WDM optical networks represent the direction to the future high capacity wide-area network applications. By reconfiguring the Logical Topology, network resources utilization can be optimized corresponding to the traffic pattern changes. From the viewpoint of network operation, the complexity of reconfiguration should be minimized as well. We consider the Logical Topology reconfiguration in arbitrary Topology IP over WDM networks with balance between network performance and operation complexity. The exact formulation of the Logical Topology reconfiguration problem is usually given as a mixed integer linear programming, but it grows intractable with increasing size of network. Here we propose a simulated annealing approach to determine the target Topology with a smaller Logical Topology change and satisfy the performance requirement. A threshold on the congestion performance requirement is used to balance the optimal congestion requirement and operation complexity by tuning this threshold to a feasible value. For an effective solution discovery, a two-stage SA algorithm is developed for multiple objectives optimization.
-
a heuristic method of Logical Topology reconfiguration in ip wdm optical networks
International Conference on Telecommunications, 2003Co-Authors: Kaoru Sezaki, Yoshiaki TanakaAbstract:WDM optical networks represent the direction to the future high capacity wide-area network applications. By creating the optical paths between several nodes in the core networks, Logical Topology can be created over the physical Topology. The network can dynamically change its Logical Topology corresponding to the changing traffic conditions. We consider the method of Logical Topology reconfiguration in wavelength routed optical networks. The exact formulation of the Logical Topology problem is usually given as a mixed integer linear programming, but it grows intractable with increasing size of network. Heuristic approaches have been proposed, here we also proposed a different heuristic approach to determine the Logical Topology reconfiguration.
Hyeongah Choi - One of the best experts on this subject based on the ideXlab platform.
-
preserving survivability during Logical Topology reconfiguration in wdm ring networks
International Conference on Parallel Processing, 2002Co-Authors: Hwajung Lee, Hongsik Choi, Suresh Subramaniam, Hyeongah ChoiAbstract:We consider the design of reconfiguring Logical topologies over physical WDM ring networks. The Logical Topology consists of the same set of nodes as the physical Topology, and the links of the Logical Topology are lightpaths established (or embedded) over the physical Topology. The Logical Topology is said survivable if the failure of any single physical link does not disconnect the Logical Topology. In this paper, we consider the following problem: Given a Logical Topology with its survivable embedding over a physical ring network and a new Logical Topology to be reconfigured, find a sequence of lightpaths additions and deletions satisfying the given wavelengths and ports constraints such that the Logical Topology remains survivable throughout the reconfiguration.
-
Logical Topology design for linear and ring optical networks
IEEE Journal on Selected Areas in Communications, 2002Co-Authors: Amrinder Arora, Suresh Subramaniam, Hyeongah ChoiAbstract:The design of Logical topologies in wavelength-routing multihop optical networks is a well-studied problem. We consider Logical Topology (LT) design over the popular ring and linear topologies. Our objective is the minimization of the electronic processing delay for the worst case traffic flow. For uniform traffic between nodes, this delay minimization corresponds to minimizing the number of hops on a shortest path between the farthest two nodes in the Logical Topology (the diameter of the Logical Topology). The simple structure of the physical topologies enables us to present a rigorous analysis of the problem. We present lower bounds for the achievable diameter wherever possible and propose practical Logical Topology design algorithms and corresponding upper bounds. We also present an application of the LT designs in the linear Topology to the survivability of ring networks.
Edoardo Bonetto - One of the best experts on this subject based on the ideXlab platform.
-
algorithms for the multi period power aware Logical Topology design with reconfiguration costs
IEEE\ OSA Journal of Optical Communications and Networking, 2013Co-Authors: Edoardo Bonetto, Filip Idzikowski, Luca Chiaraviglio, Le E RouzicAbstract:We tackle the problem of reducing power consumption in IP-over-WDM networks, targeting the power-aware Logical Topology design (LTD). Unlike the previous work in the literature, our solution reduces the power consumption with consideration of the cost (in terms of reconfigured traffic) incurred when the network is reconfigured. We first formulate the LTD with reconfiguration costs as an optimization problem. Then, we present three heuristics to effectively solve it. We compare our algorithms over an extensive set of networks and scenarios. Results indicate that our algorithms are effective in reducing power consumption while limiting the amount of traffic that is reconfigured. Moreover, we show that the input parameters are intuitive and easy to set, which makes our algorithms more practical.
-
Exploiting traffic dynamics in Power-Aware Logical Topology Design
37th European Conference and Exposition on Optical Communications, 2011Co-Authors: Edoardo Bonetto, Davide Cuda, Filip Idzikowski, Luca Chiaraviglio, Fabio NeriAbstract:We propose the Multi-Period Power-Aware Logical Topology Design. We compared two different heuristics and show that exploiting the day-night fluctuations of the traffic can lead to significant power savings at a low reconfiguration cost.
-
power aware Logical Topology design heuristics in wavelength routing networks
Optical Network Design and Modelling, 2011Co-Authors: Arsalan Ahmad, Davide Cuda, Edoardo Bonetto, Andrea Bianco, Gavilanes G Castillo, F NeriAbstract:Wavelength-Routing (WR) networks are the most common solution for core networks. With the access segment moving from copper to Passive Optical Networks (PON), core networks will become one of the major culprits of Internet power consumption. However, WR networks offer some design flexibility which can be exploited to mitigate their energy requirements. One of the main steps which has to be faced in designing WR networks is the planning of the Logical Topology (LT) starting from the matrix of traffic requests. In this paper, we propose a Mixed Integer Linear Programming (MILP) formulation to find power-wise optimal LTs. In addition, due to the complexity of the MILP approach we propose a greedy heuristic and a genetic algorithm (GA) ensuring performance close to the one achieved by the MILP formulation.
Guoliang Xue - One of the best experts on this subject based on the ideXlab platform.
-
novel survivable Logical Topology routing by Logical protecting spanning trees in ip over wdm networks
IEEE ACM Transactions on Networking, 2017Co-Authors: Zhili Zhou, Tachun Lin, K Thulasiraman, Guoliang XueAbstract:The survivable Logical Topology mapping (routing) problem in IP-over-wavelength-division multiplexing networks is to map each link in the Logical Topology (IP layer) onto a lightpath in the physical Topology (optical layer), such that failure of a physical link does not cause the Logical Topology to become disconnected. In this paper, we propose a novel approach based on the concept of protecting spanning tree set of the Logical Topology. We present necessary and sufficient conditions based on this concept and study three optimization problems with varying degrees of difficulty. We study a generalized Logical routing problem with the objective to protect the Logical Topology against maximal number of physical link failures. The new problem aims to find a survivable routing if one exists, or achieve maximal protection of physical link failures otherwise. We also show that the problem is equivalent to the minimum dominating set problem in bipartite graphs. We discuss how one can use the column generation technique to speed up the execution of this formulation, which obviates the need to find all spanning trees at the beginning of the execution of this formulation. In addition, we also present which has several nice features a heuristic approach, which incorporates a method to augment the Logical Topology with additional links to guarantee a survivable routing, which only requires a shortest path algorithm and an algorithm to generate an appropriate spanning tree. We provide the results of extensive simulations conducted to evaluate our formulations and demonstrate the effectiveness of our new approach.
-
optimum Logical Topology routing in an ip over wdm optical network and physical link failure localization an integrated approach
International Conference on Ultra Modern Telecommunications, 2013Co-Authors: Tachun Lin, K Thulasiraman, Zhili Zhou, Guoliang XueAbstract:The survivable Logical Topology routing problem for a given IP-over-WDM network is to map each Logical link into a lightpath in the physical network which guarantees connectivity of the IP network after any physical link failure. Such a survivable routing is said to protect the Logical network against all single physical link failures. But, it is possible that a Logical Topology may not admit a survivable routing. In view of this, we define a Logical Topology routing to be optimum if this routing maximizes the number of single physical link failures that do not disconnect the Logical Topology. First, we give a mixed integer linear programming formulation to determine an optimum Logical Topology routing. The failure localization problem is to localize the single physical link failures which disconnect the Logical network under a given optimum routing. Given a set of monitoring trails and the lightpath routings in an optimum routing, we give a mixed integer linear programming formulation 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.
-
novel survivable Logical Topology routing in ip over wdm networks by Logical protecting spanning tree set
International Conference on Ultra Modern Telecommunications, 2012Co-Authors: Zhili Zhou, Tachun Lin, Guoliang Xue, K Thulasiraman, Sartaj SahniAbstract:The survivable Logical Topology mapping problem in an IP-over-WDM optical network is to map each link (u, v) in the Logical Topology (at the IP layer) into a lightpath between the nodes u and v in the physical Topology (at the optical layer) such that failure of a physical link does not cause the Logical Topology to become disconnected. It is assumed that both the physical and Logical topologies are at least 2-edge connected. Generating a survivable routing is an NP-complete problem. For this problem two lines of investigations have been pursued in the literature: the mathematical programming based approach initiated by Modiano et al., and the structural approach initiated by Kurant and Thiran and pursued further by Thulasiraman et al. The mathematical programming approach is not scalable for large networks, though it gives considerable insight into certain important aspects of the problem. The structural approach requires contraction and expansion of Logical graphs and computing link-disjoint lightpaths between pairs of nodes in the physical Topology. In this paper, we propose a novel approach based on the concept of protecting spanning tree set of the Logical Topology. The basic idea is to identify a set of spanning trees of the Logical Topology and a routing of the Logical links such that at least one of these trees remains connected after a physical link failure. Given a set of trees of the Logical Topology we first present three optimization problems with varying degrees of difficulty relating to this approach and discuss their Integer Linear Programming formulations. We then consider the general case when both the tree set and a survivable routing are to be determined. For this general case we present a heuristic approach. We incorporate in this heuristic a method to augment the Logical Topology with additional links to guarantee a survivable routing. This approach has several interesting features. It only requires a shortest path algorithm and an algorithm to generate appropriate spanning trees. It also provides a framework for generating a survivable routing for the SRLG failure case. Contractions of graphs and disjoint path generation are not required that greatly reduces the computation time. We provide results of extensive simulations conducted to evaluate our new approach.
-
robustness of Logical Topology mapping algorithms for survivability against multiple failures in an ip over wdm optical network
Communication Systems and Networks, 2012Co-Authors: K Thulasiraman, Tachun Lin, Zhili Zhou, Guoliang XueAbstract:The survivable Logical Topology mapping (SLTM) problem in an IP-over-WDM optical network is to map each link (u, v) in the Logical Topology G L (at the IP layer) into a lightpath between the nodes u and v in the physical Topology G P (at the optical layer) such that failure of a physical link does not cause the Logical Topology to become disconnected. It is assumed that both the physical and Logical topologies are 2-edge connected. There are two lines of approach for the study of the SLTM problem. One approach uses Integer Linear Programming formulations. The main drawback with this approach is the use of exponential number of constraints, one for each cutset in G L . Moreover, it does not provide insight into the solution when survivability against multiple physical failures is required. The other approach, called the structural approach, uses graph theory and was pioneered by Kurant and Thiran and further generalized by us. In this paper we first present a generalized algorithmic framework for the SLTM problem. This framework includes several other frameworks considered in earlier works as special cases. We then define the concept of robustness of a mapping algorithm which captures the ability of the algorithm to provide survivability against multiple physical failures. This is similar to the concept of fault coverage used in hardware/software testing. We analyse the different frameworks for their robustness property. Using simulations, we demonstrate that even when an algorithm cannot be guaranteed to provide survivability against multiple failures, its robustness could be very high. The work also provides a basis for the design of survivability mapping algorithms when special classes of failures such as SRLG failures are to be protected against.
-
primal meets dual a generalized theory of Logical Topology survivability in ip over wdm optical networks
Communication Systems and Networks, 2010Co-Authors: K Thulasiraman, Muhammad Sufyan Javed, Guoliang XueAbstract:The survivable Logical Topology mapping (SLTM) problem in an IP-over-WDM optical network is to map each link (u, v) in the Logical Topology (at the IP layer) into a lightpath between the nodes u and v in the physical Topology (at the optical layer) such that failure of a physical link does not cause the Logical Topology to become disconnected. It is assumed that both the physical and Logical topologies are 2-edge connected. For this problem Kurant and Thiran [12] presented an algorithmic framework called SMART that involves successively contracting circuits in the Logical Topology and mapping the Logical links in the circuits into edge disjoint lightpaths in the physical Topology. In a recent work [21] we presented a dual framework involving cutsets and showed that both these frameworks possess the same algorithmic structure. Algorithms CIRCUIT-SMART, CUTSET-SMART, CUTSET-SMART-SIMPLIFIED and INCIDENCE-SMART were also presented in [21]. Effectiveness of both these frameworks as well as their robustness in providing survivability against multiple failures depends on the lengths of the cutset cover and circuit cover sequences on which they are based. To improve their effectiveness and robustness, in this paper we first introduce the concept of generalized cutset cover and generalized circuit cover sequences. We present an algorithm to get a generalized cutset (circuit) cover sequence from any given cutset (circuit) cover sequence. We then present GENCUTSET-SMART and GEN-CUTSET-SMART-SIMPLIFIED algorithms that remove some of the shortcomings of the dual framework of [21]. We prove that there is a one-to-one correspondence between the set of generalized circuit cover sequences and the set of generalized cutset cover sequences. We then show that for each execution of GEN-CIRCUIT-SMART there exists an execution of GEN-CUTSET-SMART-SIMPLIFIED such that the groups of edges that they map into edge disjoint lightpaths are exactly the same. In other words, the distinction between the primal and dual methods disappears when they use generalized sequences. Preliminary simulation results confirm our expectation that GEN-CUTSET-SMART-SIMPLIFIED will perform better than CIRCUIT-SMART and CUTSET-SMART-SIMPLIFIED (when started with a circuit or a cutset sequence) in terms of number of additional protection edges to be added.
K Thulasiraman - One of the best experts on this subject based on the ideXlab platform.
-
novel survivable Logical Topology routing by Logical protecting spanning trees in ip over wdm networks
IEEE ACM Transactions on Networking, 2017Co-Authors: Zhili Zhou, Tachun Lin, K Thulasiraman, Guoliang XueAbstract:The survivable Logical Topology mapping (routing) problem in IP-over-wavelength-division multiplexing networks is to map each link in the Logical Topology (IP layer) onto a lightpath in the physical Topology (optical layer), such that failure of a physical link does not cause the Logical Topology to become disconnected. In this paper, we propose a novel approach based on the concept of protecting spanning tree set of the Logical Topology. We present necessary and sufficient conditions based on this concept and study three optimization problems with varying degrees of difficulty. We study a generalized Logical routing problem with the objective to protect the Logical Topology against maximal number of physical link failures. The new problem aims to find a survivable routing if one exists, or achieve maximal protection of physical link failures otherwise. We also show that the problem is equivalent to the minimum dominating set problem in bipartite graphs. We discuss how one can use the column generation technique to speed up the execution of this formulation, which obviates the need to find all spanning trees at the beginning of the execution of this formulation. In addition, we also present which has several nice features a heuristic approach, which incorporates a method to augment the Logical Topology with additional links to guarantee a survivable routing, which only requires a shortest path algorithm and an algorithm to generate an appropriate spanning tree. We provide the results of extensive simulations conducted to evaluate our formulations and demonstrate the effectiveness of our new approach.
-
optimum Logical Topology routing in an ip over wdm optical network and physical link failure localization an integrated approach
International Conference on Ultra Modern Telecommunications, 2013Co-Authors: Tachun Lin, K Thulasiraman, Zhili Zhou, Guoliang XueAbstract:The survivable Logical Topology routing problem for a given IP-over-WDM network is to map each Logical link into a lightpath in the physical network which guarantees connectivity of the IP network after any physical link failure. Such a survivable routing is said to protect the Logical network against all single physical link failures. But, it is possible that a Logical Topology may not admit a survivable routing. In view of this, we define a Logical Topology routing to be optimum if this routing maximizes the number of single physical link failures that do not disconnect the Logical Topology. First, we give a mixed integer linear programming formulation to determine an optimum Logical Topology routing. The failure localization problem is to localize the single physical link failures which disconnect the Logical network under a given optimum routing. Given a set of monitoring trails and the lightpath routings in an optimum routing, we give a mixed integer linear programming formulation 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.
-
novel survivable Logical Topology routing in ip over wdm networks by Logical protecting spanning tree set
International Conference on Ultra Modern Telecommunications, 2012Co-Authors: Zhili Zhou, Tachun Lin, Guoliang Xue, K Thulasiraman, Sartaj SahniAbstract:The survivable Logical Topology mapping problem in an IP-over-WDM optical network is to map each link (u, v) in the Logical Topology (at the IP layer) into a lightpath between the nodes u and v in the physical Topology (at the optical layer) such that failure of a physical link does not cause the Logical Topology to become disconnected. It is assumed that both the physical and Logical topologies are at least 2-edge connected. Generating a survivable routing is an NP-complete problem. For this problem two lines of investigations have been pursued in the literature: the mathematical programming based approach initiated by Modiano et al., and the structural approach initiated by Kurant and Thiran and pursued further by Thulasiraman et al. The mathematical programming approach is not scalable for large networks, though it gives considerable insight into certain important aspects of the problem. The structural approach requires contraction and expansion of Logical graphs and computing link-disjoint lightpaths between pairs of nodes in the physical Topology. In this paper, we propose a novel approach based on the concept of protecting spanning tree set of the Logical Topology. The basic idea is to identify a set of spanning trees of the Logical Topology and a routing of the Logical links such that at least one of these trees remains connected after a physical link failure. Given a set of trees of the Logical Topology we first present three optimization problems with varying degrees of difficulty relating to this approach and discuss their Integer Linear Programming formulations. We then consider the general case when both the tree set and a survivable routing are to be determined. For this general case we present a heuristic approach. We incorporate in this heuristic a method to augment the Logical Topology with additional links to guarantee a survivable routing. This approach has several interesting features. It only requires a shortest path algorithm and an algorithm to generate appropriate spanning trees. It also provides a framework for generating a survivable routing for the SRLG failure case. Contractions of graphs and disjoint path generation are not required that greatly reduces the computation time. We provide results of extensive simulations conducted to evaluate our new approach.
-
robustness of Logical Topology mapping algorithms for survivability against multiple failures in an ip over wdm optical network
Communication Systems and Networks, 2012Co-Authors: K Thulasiraman, Tachun Lin, Zhili Zhou, Guoliang XueAbstract:The survivable Logical Topology mapping (SLTM) problem in an IP-over-WDM optical network is to map each link (u, v) in the Logical Topology G L (at the IP layer) into a lightpath between the nodes u and v in the physical Topology G P (at the optical layer) such that failure of a physical link does not cause the Logical Topology to become disconnected. It is assumed that both the physical and Logical topologies are 2-edge connected. There are two lines of approach for the study of the SLTM problem. One approach uses Integer Linear Programming formulations. The main drawback with this approach is the use of exponential number of constraints, one for each cutset in G L . Moreover, it does not provide insight into the solution when survivability against multiple physical failures is required. The other approach, called the structural approach, uses graph theory and was pioneered by Kurant and Thiran and further generalized by us. In this paper we first present a generalized algorithmic framework for the SLTM problem. This framework includes several other frameworks considered in earlier works as special cases. We then define the concept of robustness of a mapping algorithm which captures the ability of the algorithm to provide survivability against multiple physical failures. This is similar to the concept of fault coverage used in hardware/software testing. We analyse the different frameworks for their robustness property. Using simulations, we demonstrate that even when an algorithm cannot be guaranteed to provide survivability against multiple failures, its robustness could be very high. The work also provides a basis for the design of survivability mapping algorithms when special classes of failures such as SRLG failures are to be protected against.
-
Logical Topology survivability in ip over wdm networks survivable lightpath routing for maximum Logical Topology capacity and minimum spare capacity requirements
Design of Reliable Communication Networks, 2011Co-Authors: Zhili Zhou, K ThulasiramanAbstract:The survivable Logical Topology mapping problem in an IP-over-WDM optical network is to map each link (u, v) in the Logical Topology (at the IP layer) into a lightpath between the nodes u and v in the physical Topology (at the optical layer) such that failure of a physical link does not cause the Logical Topology to become disconnected. It is assumed that both the physical and Logical topologies are 2-edge connected. For this problem two lines of investigations have been pursued in the literature: one pioneered by Modiano et al., and the other pioneered by Kurant and Thiran. Since then there have been a great deal of research on this problem. Most of the works have not considered limitations imposed on the routings by physical capacity limits. In this paper, we first introduce two concepts: weakly survivable routing and strongly survivable routing. We then provide mathematical programming formulations for two problems. Problem 1 is to design a survivable lightpath routing that maximizes the Logical capacity available before and after a physical link failure. The second problem is to add spare capacities to the physical links to guarantee routability of all Logical link demands before and after a physical link failure. The frameworks provided by our formulation can be used to accommodate other scenarios such as those involving load balancing and fair capacity allocation constraints. We conclude with simulations that compare the results using these formulations and those obtained by heuristics that mitigate the computational complexity of the mathematical programming formulations.
