Preliminary Program

Developing optical network optimization algorithms involves representing many different instances related to the network itself: topology, physical layer equipment found in nodes, links, etc. It also requires description of traffic demand. We propose onML; an XML-based structure to fulfill such requirements. The onML structure is used by ONDE, a development environment targeted at optimization algorithms for optical networks. A sought feature of ONDE is a modular design allowing a clear separation of onML files parsing functions, graphical user interfaces and network optimization programs. With such a modular approach, multiple research teams can cooperate to develop and easily share new tools and algorithms. As a result, an XML parser is tailored to parse data in onML-compliant files and is easily interfaced with the main C++ optimization algorithm under development. For graphical user interface aspects, the ONDE environment uses a Java program which is interfaced with the XML parser through the Java Native Interface (JNI).

On Column Generation Formulations for the RWA Problem

Brigitte Jaumard, CIISE, Concordia University

Optimizing Compensation While Solving the GRWA Problem

Brigitte Jaumard, CIISE, Concordia University

Alain C. Houle, ECE, Université de Sherbrooke

Video-on-demand (VoD) service providers are intensely interested in transport, storage, streaming and caching in content delivery networks. Today's 5,000-hour library may grow toward the 750,000-hour "Long Tail" movie and TV-series catalog. We propose a method, and demonstrate a tool, to calculate how much of a library should be cached. Much previous work focused on theoretical caching concepts, or the dynamics of cache filling and reclamation. Our method, instead, explicitly considers the impact of the available video server equipment; we present a VoD design tool comprising a novel cost function, hit ratio estimation technique and heuristic.

Online Anomaly Detection for Optical Networks Tarem Ahmed, McGill University Mark Coates, ECE, McGill University
	High-speed optical backbones are constantly hit by network anomalies. These anomalous events span a wide variety of types, from denial-of-service attacks and viruses to large data transfers. Some anomalies are intentionally malicious, while others may be accidental. This necessitates the need for an online and instantaneous anomaly detection mechanism for high-speed optical networks. We propose such a scheme, based on the kernel version of the celebrated Recursive Least-Squares algorithm. Different types of anomalies affect the network in different ways, and it is also not always possible to know a priori, how a potential anomaly would exhibit itself in traffic statistics. Our algorithm learns the characteristics of normal traffic behavior, and then raises an alarm immediately upon encountering a deviation from the norm. We test our algorithm on data from the Abilene backbone network.

ONDE: A Generic XML-Based Development Environment for Optimization of WDM Optical Networks Mehdi Haïtami, Ghyslain Abel, Alain C. Houle, ECE, Université de Sherbrooke Brigitte Jaumard, CIISE, Concordia University
	Developing optical network optimization algorithms involves representing many different instances related to the network itself: topology, physical layer equipment found in nodes, links, etc. It also requires description of traffic demand. We propose onML; an XML-based structure to fulfill such requirements. The onML structure is used by ONDE, a development environment targeted at optimization algorithms for optical networks. A sought feature of ONDE is a modular design allowing a clear separation of onML files parsing functions, graphical user interfaces and network optimization programs. With such a modular approach, multiple research teams can cooperate to develop and easily share new tools and algorithms. As a result, an XML parser is tailored to parse data in onML-compliant files and is easily interfaced with the main C++ optimization algorithm under development. For graphical user interface aspects, the ONDE environment uses a Java program which is interfaced with the XML parser through the Java Native Interface (JNI).

Wavelength Assignment for Multicasts in Star Networks Omid Amini, Florian Huc, Frederic Havet et Stephan Thomasse, INRIA, CNRS, and UNSA
	We study the wavelength assignment for multicasts in star network. We are given a star network in which a center node is connected to a set of nodes V by n fibers. Each node v sends a set of s(v) multicasts to the sets of nodes S₁(v), ..., S_s(v)(v). We model the problem has a graph problem. The graph we consider has V has vertex set. Moreover for each multicast (v,S_i(v)) we add the set of arcs A⁺_i(v) = {vw, w Î S_i(v) } with label i. The problem is to find a n-fiber wavelength assignment of D using as few wavelengths as possible. That is to assign to each arcs a wavelength such that for any wavelength w, at a vertex v, the number of incoming arcs of this wavelength w plus the number of labels with at least one outgoing arc of this wavelength w is less than the number n of fibers.

RWA Dimensioning in a WDM Network with OXCs and MSPPs Alain C. Houle, GEGI, Université de Sherbrooke Brigitte Jaumard, CIISE, Concordia University Abdallah Jarray, DIRO, Université de Montréal
	We study a scalable design for WDM networks with OXCs and MSPPs. We set a mathematical programming model that allows the definition of the best switching capacity of OXCs and MSPPs for a given traffic, and the dimensioning of the WDM network in order of the routing and wavelength assignments. In order to solve the resulting model, we propose to use branch-and-price algorithms, i.e., column generation techniques combined with branch-and-bound methods.

Dynamic Traffic Grooming Alain C. Houle, GEGI, Université de Sherbrooke Brigitte Jaumard, CIISE, Concordia University Ammar Metnani, DIRO, Université de Montréal Romaric Boley, Université de Technologie de Compiègne
	We present different scenarios based on a dynamic grooming policy for WDM mesh networks. it goes from a first scenario where no perturbation is allowed for the users to a scenario where we allow to reset grooming, routing and wavelength assignment in order to minimize the blocking rate and the costs. Clearly, a compromise has to be found taking into account the scalability of the selected solution scheme, and its resulting cost.

On Column Generation Formulations for the RWA Problem Brigitte Jaumard, CIISE, Concordia University Christophe Meyer, CRT & GERAD, Université de Montréal Babacar Thiongane, DIRO, Université de Montréal
	We present a review of column generation formulations for the Routing and Wavelength Assignment (RWA) problem with the objective of minimizing the blocking rate. Several improvements are proposed together with a comparison of the different formulations with respect to the quality of their continuous relaxation bounds and their computing solution ease.

Optimizing Compensation While Solving the GRWA Problem Brigitte Jaumard, CIISE, Concordia University Alain C. Houle, ECE, Université de Sherbrooke Yannick Solari, DIRO, Université de Montréal
	Recent development of WDM Multiplexing led to a significant increase of transmission capacity broadband networks. While there is now no limitation in the transmission capacity, attention should be now given to the interconnection capacity, i.e., routing and switching capabilities. For this reason, a lot of attention has been devoted to the GRWA - Grooming, Routing and Wavelength Assignment problem with the objective of either minimizing the capacity or the interconnecting equipment cost. In this study, we include the compensation concerns when solving the GRWA problem and propose a multi-phase Tabu Search to solve the resulting design problem. Numerical experiments were conducted on various network topologies and traffic instances. Results showed that the minimum overall cost is not necessarily reached with the minimum MSPP cost.

Video-on-demand equipment allocation Mark Coates, ECE, McGill University Frederic Thouin, ECE, McGill University
	Video-on-demand (VoD) service providers are intensely interested in transport, storage, streaming and caching in content delivery networks. Today's 5,000-hour library may grow toward the 750,000-hour "Long Tail" movie and TV-series catalog. We propose a method, and demonstrate a tool, to calculate how much of a library should be cached. Much previous work focused on theoretical caching concepts, or the dynamics of cache filling and reclamation. Our method, instead, explicitly considers the impact of the available video server equipment; we present a VoD design tool comprising a novel cost function, hit ratio estimation technique and heuristic.

Backup Path Re-optimizations for Shared Path Protection in Multi-domain Networks Brigitte Jaumard, CIISE, Concordia University Linh Truong, DIRO, Université de Montréal
	Within the context of dynamic routing models for shared path protection in multi-domain networks, we propose a backup path re-optimization phase with possible rerouting of the existing backup paths in order to increase the bandwidth sharing among them while minimizing the network backup cost. The re-optimization phase is activated periodically or when routing a new connection fails because of insufficient capacity. Three re-optimization models are discussed: i) Local rerouting where the re-optimization is serially performed on selected domains, and ii) Local rerouting with least effort, i.e., where the smallest possible number of backup path reroutings is performed in order to be able to handle new connection requests, iii) Local reroutings with least effort upon blocking. Comparative performance of the three models is conducted and numerical results are presented.

Traffic Grooming in WDM Mesh Optical Networks: a mathematical formulation Brigitte Jaumard, CIISE, Concordia University François Vanderbeck, Université de Bordeaux Benoit Vignac, DIRO, Université de Montréal
	Traffic grooming capability gives a better use of the available network capacity in current optical networks as many connections with different end nodes can share the capacity of a given wavelength on a given optical fiber. However, to operate involved O/E/O conversions, we have to install optical ports at nodes where the grooming pattern has to be changed. As optical ports are very expensive, address the grooming, routing and wavelength assignment (GRWA) so as to minimize the overall number of ports becomes a big issue. We present a mathematical formulation that exploit the decomposability of the problem: as we assume that each request is routed over the same wavelength along its working path, each wavelength are independent from each other. We define an independant routing configuration (IRC) as a routing pattern over a single wavelength and we can formulate the GRWA as selecting no more than W IRC, where W is the number of available wavelength, to satisfy all the requests, while minimizing the total number of optical ports. We will present the main steps to solve the resulting integer linear programming formulations.

Multilayer Dynamic Traffic Grooming and Routing with an IP/MPLS Layer Anjali Agarwal, ECE, Concordia University Brigitte Jaumard, CIISE, Concordia University Nadia Zabehi, ECE, Concordia University
	Interoperability between WDM networks and IP networks becomes a major concern in third generation WDM networks. Huge bandwidth capacity of WDM networks with dominance of IP technology makes the blend a future proof combination .Integrated routing and wavelength assignment known as Generalized MPLS (GMPLS) starts to emerge. Problem of traffic granularity mismatch between IP and WDM layer also has been addressed as an important issue and different proposals have been made to overcome this problem. In this survey, the topological and technological evolution of optical networks will be studied and essence of traffic grooming will be reviewed. GRWA and GMPLS as potential approaches to solve and optimize the traffic grooming problem will be addressed and examples of related works will be presented. Finally future directions and open issues will be summarized.