Light trees: optical multicasting for improved performance inwavelength routed networks

We introduce the concept of a light-tree in a wavelength-routed optical network. A light-tree is a point-to-multipoint generalization of a lightpath. A lightpath is a point-to-point all-optical wavelength channel connecting a transmitter at a source node to a receiver at a destination node. Lightpath communication can significantly reduce the number of hops (or lightpaths) a packet has to traverse; and this reduction can, in turn, significantly improve the network's throughput. We extend the lightpath concept by incorporating an optical multicasting capability at the routing nodes in order to increase the logical connectivity of the network and further decrease its hop distance. We refer to such a point-to-multipoint extension as a light-tree. Light-trees can not only provide improved performance for unicast traffic, but they naturally can better support multicast traffic and broadcast traffic. In this study, we shall concentrate on the application and advantages of light-trees to unicast and broadcast traffic. We formulate the light-tree-based virtual topology design problem as an optimization problem with one of two possible objective functions: for a given traffic matrix, (i) minimize the network-wide average packet hop distance, or (ii) minimize the total number of transceivers in the network. We demonstrate that an optimum light-tree-based virtual topology has clear advantages over an optimum lightpath-based virtual topology with respect to the above two objectives     

Traffic grooming in WDM ring networks to minimize the maximum electronic port cost

We consider the problem of traffic grooming in WDM ring networks. Traffic grooming is a variant of the well-known logical topology design problem, and is concerned with the development of techniques for combining low speed traffic components onto high speed channels in order to minimize network cost. Previous studies have focused on aggregate representations of the network cost. In this work, we consider a Min-Max objective, in which it is desirable to minimize the cost at the node where this cost is maximum. Such an objective is of high practical value when dimensioning a network for unknown future traffic demands and/or for dynamic traffic scenarios. We present new theoretical results which demonstrate that traffic grooming with the Min-Max objective is NP-complete even when wavelength assignment is not an issue. We also present new polynomial-time traffic grooming algorithms for minimizing the maximum electronic port cost in both unidirectional and bidirectional rings. We evaluate our algorithms through experiments with a wide range of problem instances, by varying the network size, number of wavelengths, traffic load, and traffic pattern. Our results indicate that our algorithms produce solutions which are always close to the optimal and/or the lower bound, and which scale well to large network sizes, large number of wavelengths, and high loads. We also demonstrate that, despite the focus on minimizing the maximum cost, our algorithms also perform well in terms of the aggregate electronic port cost over all ring nodes.     

Logical topology design for dynamic traffic grooming in WDM optical networks

Traffic grooming in optical networks refers to consolidation of subwavelength client connections onto lightpaths. Depending on whether client connections are given in advance or randomly arrive/depart, traffic grooming is classified as static and dynamic. Dynamic traffic grooming has been traditionally performed through establishing/releasing lightpaths online. In this paper, the authors propose an alternate approach to design a static logical topology a priori and then route randomly arriving client connections on it to avoid frequent lightpath setup/teardown. Two problems are considered: 1) minimize resource usage constrained by traffic blocking requirements and 2) maximize performance constrained by given resources. These are formulated as integer linear-programming (ILP) problems. The numerical results show that the resource usage dramatically decreases when the blocking requirement is relaxed, and the grooming performance slowly increases when given more resources. In addition, the number of ports at client nodes has more profound impact on traffic grooming than the number of wavelengths.     

Performance analysis of multicast routing and wavelength assignment protocol with dynamic traffic grooming in WDM networks

The need for on‐demand provisioning of wavelength‐routed channels with service‐differentiated offerings within the transport layer has become more essential because of the recent emergence of high bit rate Internet protocol (IP) network applications. Diverse optical transport network architectures have been proposed to achieve the above requirements. This approach is determined by fundamental advances in wavelength division multiplexing (WDM) technologies. Because of the availability of ultra long‐reach transport and all‐optical switching, the deployment of all‐optical networks has been made possible. The concurrent transmission of multiple streams of data with the assistance of special properties of fiber optics is called WDM. The WDM network provides the capability of transferring huge amounts of data at high speeds by the users over large distances. There are several network applications that require the support of QoS multicast, such as multimedia conferencing systems, video‐on‐demand systems, real‐time control systems, etc. In a WDM network, the route decision and wavelength assignment of lightpath connections are based mainly on the routing and wavelength assignment (RWA). The multicast RWA's task is to maximize the number of multicast groups admitted or minimize the call‐blocking probability. The dynamic traffic‐grooming problem in wavelength‐routed networks is generally a two‐layered routing problem in which traffic connections are routed over lightpaths in the virtual topology layer and lightpaths are routed over physical links in the physical topology layer. In this paper, a multicast RWA protocol for capacity improvement in WDM networks is designed. In the wavelength assignment technique, paths from the source node to each of the destination nodes and the potential paths are divided into fragments by the junction nodes and these junction nodes have the wavelength conversion capability. By using the concept of fragmentation and grouping, the proposed scheme can be generally applied for the wavelength assignment of multicast in WDM networks. An optimized dynamic traffic grooming algorithm is also developed to address the traffic grooming problem in mesh networks in the multicast scenario for maximizing the resource utilization and minimizing the blocking probability. Copyright © 2011 John Wiley & Sons, Ltd.     

Cost efficient traffic grooming and regenerator placement in impairment-aware optical WDM networks

In this paper, we address the problem of traffic grooming and regenerator placement in a WDM optical network in which lightpaths are hop-constrained by physical impairments. The efficient placement of regenerators and electronic grooming equipment at ROADM nodes for a given network topology is required such that all traffic demands can be supported with minimum cost. We present a detailed ROADM node architecture together with an associated cost model. We model the problem by Integer Linear Programming (ILPs) and propose an auxiliary-graph-based heuristic for jointly placing regenerators and electronic grooming equipment in the network. To evaluate the performance of the proposed heuristic, we also derive a lower bound on the network cost. The numerical results show that combining the grooming problem with the placement of regenerators reduces the network cost significantly compared to the cases in which traffic grooming and regenerator placement are handled separately. The performance of the proposed polynomial-time heuristic is very close to the lower bound and approaches the bound as the network load increases.     

Design of grooming architectures for optical WDM mesh networks: limited grooming with electronic wavelength conversion

In this article, we consider the problem of traffic grooming in optical wavelength division multiplexed (WDM) mesh networks under static traffic conditions. The objective of this work is to minimize the network cost and in particular, the electronic port costs incurred for meeting a given performance objective. In earlier work, we have shown the benefits of limited grooming switch architectures, where only a subset of wavelengths in a network are equipped with expensive SONET Add Drop Multiplexers (SADM) that provide the grooming functionality. In this work, we also consider the wavelength conversion capability of such groomers. This can be achieved using a digital cross-connect (DCS) in the grooming switch to switch low-speed connections between the SADMs (and hence, between wavelengths). The grooming switch thus avoids the need for expensive optical wavelength converters. Based on these observations, we propose a limited conversion-based grooming architecture for optical WDM mesh networks. The local ports at every node in this architecture can be one of three types: an add-drop port, a grooming port that allows wavelength conversion or a grooming port that does not allow wavelength conversion. The problem studied is: given a static traffic model, where should the different ports be placed in a network? We formulate this as an optimization problem using an Integer Linear Programing (ILP) and present numerical results for the same. We also present a heuristic-based approach to solve the problem for larger networks.     

Algorithms for the global design of WDM networks including the traffic grooming

In this paper, we propose a model and algorithms for the global design problem of wavelength division multiplexing (WDM) networks including the traffic grooming. This problem consists in finding the number of fibres between each pair of nodes (i.e. the physical topology), finding the number of transponders at each node, choosing the set of lightpaths (i.e. the virtual topology), routing these lightpaths over the physical topology and, finally, grooming and routing the traffic over the lightpaths. Since this problem is NP-hard, we propose two heuristic algorithms and a tabu search metaheuristic algorithm to find solutions for real-size instances within a reasonable amount of computational time.     

A Lagrangian-Relaxation Based Network Profit Optimization For Mesh SONET-Over-WDM Networks

In Wavelength Division Multiplexing (WDM) networks, the huge capacity of wavelength channels is generally much larger than the bandwidth requirement of individual traffic streams from network users. Traffic grooming techniques aggregate low-bandwidth traffic streams onto high-bandwidth wavelength channels. In this paper, we study the optimization problem of grooming the static traffic in mesh Synchronous Optical Network (SONET) over WDM networks. The problem is formulated as a constrained integer linear programming problem and an innovative optimization objective is developed as network profit optimization. The routing cost in the SONET and WDM layers as well as the revenue generated by accepting SONET traffic demands are modelled. Through the optimization process, SONET traffic demands will be selectively accepted based on the profit (i.e., the excess of revenue over network cost) they generate. Consiering the complexity of the network optimization problem, a decomposition approach using Lagrangian relaxation is proposed. The overall relaxed dual problem is decomposed into routing and wavelength assignment and SONET traffic routing sub-problems. The subgradient approach is used to optimize the derived dual function by updating the Lagrange multipliers. To generate a feasible network routing scheme, a heuristic algorithm is proposed based on the dual solution. A systematic approach to obtain theoretical performance bounds is presented for an arbitrary topology mesh network. This is the first time that such theoretical performance bounds are obtained for SONET traffic grooming in mesh topology networks. The optimization results of sample networks indicate that the roposed algorithm achieves good sub-optimal solutions. Finally, the influence of various network parameters is studied.     

Reducing electronic multiplexing costs in SONET/WDM rings with dynamically changing traffic

In this paper, we consider traffic grooming in WDM/SONET ring networks when the offered traffic is characterized by a set of traffic matrices. Our objective is to minimize the cost of electronic add/drop multiplexers (ADMs) in the network, while being able to support any offered traffic matrix in a rearrangeably nonblocking manner. We provide several methods for reducing the required number of ADMs for an arbitrary class of traffic matrices. We then consider the special case where the only restriction on the offered traffic is a constraint on the number of circuits a node may source at any given time. For this case, we provide a lower bound on the number of ADMs required and give conditions that a network must satisfy in order for it to support the desired set of traffic patterns. Circuit assignment and ADM placement algorithms with performance close to this lower bound are provided. These algorithms are shown to reduce the electronic costs of a network by up to 27%. Finally, we discuss extensions of this work for supporting dynamic traffic in a wide-sense or strict sense nonblocking manner as well as the benefits of using a hub node and tunable transceivers. Much of this work relies on showing that these grooming problems can often be formulated as standard combinatorial optimization problems.     

Some principles for designing a wide-area WDM optical network

We explore design principles for next-generation optical wide-area networks, employing wavelength-division multiplexing (WDM) and targeted to nationwide coverage. This optical network exploits wavelength multiplexers and optical switches in routing nodes, so that an arbitrary virtual topology may be embedded on a given physical fiber network. The virtual topology, which is used as a packet-switched network and which consists of a set of all-optical “lightpaths”, is set up to exploit the relative strengths of both optics and electronics-viz. packets of information are carried by the virtual topology “as far as possible” in the optical domain, but packet forwarding from lightpath to lightpath is performed via electronic switching, whenever required. We formulate the virtual topology design problem as an optimization problem with one of two possible objective functions: (1) for a given traffic matrix, minimize the network-wide average packet delay (corresponding to a solution for present traffic demands), or (2) maximize the scale factor by which the traffic matrix can be scaled up (to provide the maximum capacity upgrade for future traffic demands). Since simpler versions of this problem have been shown to be NP-hard, we resort to heuristic approaches. Specifically, we employ an iterative approach which combines “simulated annealing” (to search for a good virtual topology) and “flow deviation” (to optimally route the traffic-and possibly bifurcate its components-on the virtual topology). We do not consider the number of available wavelengths to be a constraint, i.e., we ignore the routing of lightpaths and wavelength assignment for these lightpaths. We illustrate our approaches by employing experimental traffic statistics collected from NSFNET     

Forming optimal topologies for Bluetooth-based wireless personal area networks

In this paper, we address the problem of determining an optimal topology for Bluetooth wireless personal area networks (BT-WPANs). In BT-WPANs, multiple communication channels are available, through a frequency hopping technique. The way network nodes are grouped to share the same channel, and which nodes are selected to bridge traffic from a channel to another, has a significant impact on the capacity and throughput of the system, as well as the nodes' battery lifetime. The determination of an optimal topology is thus extremely important. Our approach is based on a min-max formulation of the optimization problem, which produces topologies that minimize the traffic load of the most congested node in the network (thus also minimizing energy consumption) while meeting the traffic requirements and the constraints posed by the BT-WPAN technology. We investigate the performance of the topologies produced by our optimization approach as the system requirements vary, and evaluate the trade-offs existing between system complexity and network efficiency. Results show that a topology optimized for some traffic requirements is remarkably robust to changes in the traffic pattern. Due to the problem complexity, the optimal solution is attained in a centralized manner. Although this implies severe limitations, a centralized solution can be applied whenever a network coordinator is elected, and provides a useful term of comparison for any distributed heuristics.     

On Hierarchical Traffic Grooming in WDM Networks

The traffic grooming problem is of high practical importance in emerging wide-area wavelength division multiplexing (WDM) optical networks, yet it is intractable for any but trivial network topologies. In this work, we present an effective and efficient hierarchical traffic grooming framework for WDM networks of general topology, with the objective of minimizing the total number of electronic ports. At the first level of hierarchy, we decompose the network into clusters and designate one node in each cluster as the hub for grooming traffic. At the second level, the hubs form another cluster for grooming intercluster traffic. We view each (first- or second-level) cluster as a virtual star, and we present an efficient near-optimal algorithm for determining the logical topology of lightpaths to carry the traffic within each cluster. Routing and wavelength assignment is then performed directly on the underlying physical topology. We demonstrate the effectiveness of our approach by applying it to two networks of realistic size, a 32-node, 53-link topology and a 47-node, 96-link network. Comparisons to lower bounds indicate that hierarchical grooming is efficient in its use of the network resources of interest, namely, electronic ports and wavelengths. In addition to scaling to large network sizes, our hierarchical approach also facilitates the control and management of multigranular networks.      

Strategies for optimal logical topology design and traffic grooming

Traffic grooming techniques are used to combine low-speed data streams onto high-speed lightpaths with the objective of minimizing the network cost, or maximizing the network throughput. In this article, we present a complete suite of efficient Integer Linear Program (ILP) formulations for logical topology design and traffic grooming on mesh WDM networks. Our formulations can be easily modified to implement different objective functions and, contrary to previous formulations, our ILP formulation can be used to generate optimal solutions for practical sized networks with hundreds of requests. Our first set of formulations addresses the complete logical topology design traffic grooming problem, including RWA and traffic routing. The second set uses the simplifying assumption that RWA is not an issue. The last two sets address optimal traffic grooming alone, where the logical topology is already specified. We have studied these formulations, using simulation with networks having up to 30 nodes, and with hundreds and, in some cases, over a thousand low-speed data streams and have shown that the formulations are able to generate optimal solutions within a reasonable amount of time.     

A novel generic graph model for traffic grooming in heterogeneous WDM mesh networks

As the operation of our fiber-optic backbone networks migrates from interconnected SONET rings to arbitrary mesh topology, traffic grooming on wavelength-division multiplexing (WDM) mesh networks becomes an extremely important research problem. To address this problem, we propose a new generic graph model for traffic grooming in heterogeneous WDM mesh networks. The novelty of our model is that, by only manipulating the edges of the auxiliary graph created by our model and the weights of these edges, our model can achieve various objectives using different grooming policies, while taking into account various constraints such as transceivers, wavelengths, wavelength-conversion capabilities, and grooming capabilities. Based on the auxiliary graph, we develop an integrated traffic-grooming algorithm (IGABAG) and an integrated grooming procedure (INGPROC) which jointly solve several traffic-grooming subproblems by simply applying the shortest-path computation method. Different grooming policies can be represented by different weight-assignment functions, and the performance of these grooming policies are compared under both nonblocking scenario and blocking scenario. The IGABAG can be applied to both static and dynamic traffic grooming. In static grooming, the traffic-selection scheme is key to achieving good network performance. We propose several traffic-selection schemes based on this model and we evaluate their performance for different network topologies.     

An optimal design method for magnetic resonance imaging gradient waveforms

A method of using nonlinear constrained optimization to design gradient waveforms for magnetic resonance imaging is described. Formulation and solution of the waveform optimization problem are described and example waveforms are presented for a variety of design objectives and constraint sets. Most design objectives can be expressed as linear or quadratic functions of the discrete parameter set, and most constraint functions are linear. Thus, linear and quadratic programming techniques can be utilized to solve the optimization problem. Among the objectives considered are: minimize RMS current; minimize waveform slewing; minimize waveform moments to reduce motion induced dephasing; minimize echo time (TE) for given imaging and motion refocusing conditions; maximize the gradient amplitude during RF application and sampling and the area of the phase encoding waveform to maximize resolution; and minimize or maximize the gradient b factor or diffusion sensitivity. This optimal design procedure produces physically realizable waveforms which optimally achieve specific imaging and motion artifact reduction goals, and it is likely to reduce waveform design time by making it more scientifically (rather than heuristically) based.     

Design of wavelength-routed optical networks for packet switchedtraffic

We consider the problem of designing a logical optical network topology for a given physical topology (or fiber layout) and a given traffic demand matrix between the end-users. Traffic between the end-users is carried in a packet-switched form and the objective of our logical topology design is to minimize the maximum congestion on the logical connections in the logical topology. The logical connections are realized by wavelength continuous paths or lightpaths between end-users and they are routed via wavelength-selective routers. Note that a topology with lower maximum link congestion will allow its traffic demand matrix to be scaled up by a larger factor. In the logical topology each node is equipped with a limited number of optical transceivers, hence logical connections cannot be set up between every pair of nodes. In this paper we present an improved lower bound for maximum congestion on any link In the logical topology. The bound is shown to be up to 50% higher than the existing ones. An analytical model for obtaining the maximum and average logical connection loads for a given logical network and traffic demand matrix is also formulated, and it has been confirmed via simulation. Finally, two heuristic algorithms for constructing a logical topology that reduces maximum logical connection congestion are presented     

Multicast multi-granular grooming based on integrated auxiliary grooming graph in optical networks

In order to improve the bandwidth utilization efficiency and reduce the blocking probability for multicast requests in optical networks, the multicast traffic grooming approach was proposed to groom a lot of low-speed traffic to a few of high-speed light-trees. At the same time, in order to save the ports and the cost of optical cross-connect, the multicast waveband grooming approach was proposed to groom multiple light-trees to a few of waveband tunnels. However, the existing approaches all did not consider the joint performances of improving bandwidth utilization efficiency, reducing blocking probability and saving ports for multicast requests. Therefore, in this article, we propose a new multicast multi-granular grooming approach to perform the hierarchical sequential grooming to improve the joint performances based on a newly developed integrated auxiliary grooming graph (IAGG) that includes multiple wavelength integrated grooming graphs (WIGGs) and one waveband virtual topology layered graph (BVLG) to support both the multicast traffic grooming and multicast waveband grooming. In order to achieve the map of light-tree to the virtual topology layer in WIGG or BVLG, we present a light-segment map method, where a light-tree will be divided to several light-segments each of which will be independently mapped to the virtual topology layer. Since different definitions of blocking probability may lead to different objectives, we define two kinds of blocking probability, mean blocking probability of requests (MBPR) and mean blocking probability of users (MBPU). According to the two definitions of blocking probability, we propose two multicast multi-granular grooming heuristic algorithms, Heuristic Algorithm with minimizing MBPR and Heuristic Algorithm with minimizing MBPU based on IAGG. Simulation results show that the two proposed algorithms are both efficient and have better performances than traditional multicast grooming algorithm.     

Traffic grooming in mesh WDM optical networks - performance analysis

Traffic grooming is an important task in interworking between the wavelength-division multiplexing (WDM) optical network that supplies "pipes" at the wavelength granularity, and the attached client networks that usually require connections of subwavelength granularity. The focus of this paper is to conduct performance analysis of grooming dynamic client traffic in WDM optical networks with a mesh topology. This paper first briefly introduces the traffic grooming problem in WDM optical networks and the issues related to performance analysis. It then develops two link blocking models, an exact model based on the stochastic knapsack problem and an approximation model based on an approximate continuous time Markov chain (CTMC). The end-to-end performance analysis is conducted using the reduced load approximation. The result obtained from analysis is shown to be accurate compared with the numerical result obtained from simulation.     

Topology control for multi-channel multi-radio wireless mesh networks using directional antennas

Directional antennas are widely used technologies for reducing signal interference and increasing spatial reuse. In this paper, we propose a topology control method for multi-channel multi-radio wireless mesh networks that use directional antennas. We are given a set of mesh routers installed in a region and some of them are gateway nodes that are connected to the Internet via wired lines. Each router has a traffic demand (Internet access traffic) generated from the end-users. The problem is how to adjust antenna orientations of radios and assign channels to them to construct a logical network topology, such that the minimum delivery ratio of traffic demands of routers is maximized. We first formulate the problem to an equivalent optimization problem with a clearer measurable metric, which is to minimize the largest interfering traffic of links in the network. We then propose a three-step solution to solve the problem. Firstly, we construct a set of routing trees, with the objective to balance the traffic among tree links. Secondly, we assign the radios of a node to the links it needs to serve, such that the total traffic load of the links that each radio serves is as balanced as possible. Thirdly, we do a fine-grained adjustment of antenna orientations and assign channels to them, such that the transmission area of each antenna will cover all the links it serves and the largest interfering traffic of links is minimized.     

IPoverWDM光网络中基于滑动调度业务模型的节能业务量疏导算法研究(英文)

In this paper,we investigate on the problem of energy-efficient traffic grooming under sliding scheduled traffic model for IP over WDM optical networks,so as to minimize the total energy consumption of the core network.We present a two-layer auxiliary graph model and propose a new energyefficient traffic grooming heuristic named Two-Dimension Green Traffic Grooming(TDGTG) algorithm,which takes both space and time factors into consideration for network energy efficiency.We compare our proposed TDGTG algorithm with the previous traffic grooming algorithms for scheduled traffic model in terms of total energy consumption and blocking probability.The simulation results in three typical carrier topologies show the efficiency of our proposed TDGTD algorithm.