Quality of Service Routing using Decentralized Learning

Fariba Heidari, Dept. Electrical and Computer Engineering , McGill University

Lorne Mason, Dept. Electrical and Computer Engineering , McGill University

1

Adaptive routing plays an important role in on-line QoS provisioning. In this work, we present reinforcement learning based algorithms for decentralized adaptive routing. The presented routing schemes only use their locally observed events and update their routing policy using learning schemes. Discrete event simulation results show the merit of these algorithms in terms of increasing the network admissibility compared with the shortest path routing.

While in general the performance degradation due to decentralized routing as opposed to centralized system optimal routing policies can be arbitrarily large, it is of interest to examine this gap in practical scenarios. We provide the nonlinear programming formulations of these problems along with a distributed recursive approach to compute the solutions. The results of this study indicate that decentralized learning techniques provide efficient, stable and scalable approaches for adaptive routing.

Fiber-Wireless (FiWi) Access Networks

Navid Ghazisaidi, Institut National de la Recherche Scientifique (INRS) - ÉMT 

Martin Maier, Institut National de la Recherche Scientifique (INRS) - ÉMT 

2

Today’s access networks are limited in terms of efficient and dynamic bandwidth provisioning and availability. Fiber-to-the-home (FTTH) access networks solve the first/last mile bandwidth bottleneck by means of providing high-speed connections for bandwidth-hungry users.

Hybrid fiber-wireless (FiWi) access networks intend to combine the huge amount of available bandwidth of optical fiber networks and the ubiquity of wireless access networks with the objective to reduce their cost and complexity.

Fiber optic and wireless access networks may use different control protocols to arbitrate channel access. Further, different traffic classes are defined for each type of access network which must be mapped to each other. Protocol translation and mapping in FiWi networks can be done in two ways: (i) Radio and Fiber (R&F) and (ii) Radio over Fiber (RoF).

This poster highlights key enabling optical as well as wireless technologies and explains their role in emerging FiWi access networks. With a focus on EPON as a powerful optical access network and two recent wireless access technologies, i.e., WiFi and WiMAX, different architectures of FiWi access networks are shown and explained. Moreover, using the capabilities of wireless mesh networks (WMNs) based on both WiMAX and/or WiFi renders the access network more robust, whereby multipath routing helps enhance the availability of the network significantly. To improve bandwidth-efficiency, powerful load balancing and reconfiguration techniques may be used in FiWi networks by means of WDM PONs.

Optimal Switching Architecture Design in Agile Photonic Networks

Alain C. Houle, GEGI, Université de Sherbrooke
Brigitte Jaumard, CIISE, Concordia University

Abdallah Jarray, DIRO, Université de Montréal 

3

We investigate the design of an agile SONET-WDM optical backbone network through a generic nodal configuration where agility is a combination of electrical and photonic equipment. We assume that each node is equipped with a MultiService Provisioning Platform (MSPP) and a Photonic Cross-Connect (PXC). The objective of the study is to find their optimal dimensioning for various dynamic traffic patterns. It consists in finding a feasible bandwidth provisioning for as many requests as possible, i.e., routing and assigning wavelengths to requests, while minimizing the equipment cost where the cost is estimated by the number of MSPP transport blades for the MSPP equipment, by the number of PXCs Input/Output ports and the number of MEMS mirrors for the photonic switching equipment.
We establish a mathematical model which makes use of large scale optimization tools and propose two heuristics in order to solve it efficiently. The first one is a myopic rounding heuristic where network resources are selected as needed and the second one is an anticipative rounding heuristic where network resources are planned of time assuming future behaviors of the customers are known. The performance of both heuristics is compared in terms of cost saving and grade of service, and against a greedy heuristic proposed previously by the authors.

Alain C. Houle, GEGI, Université de Sherbrooke
Brigitte Jaumard, CIISE, Concordia University

Ammar Metnani, DIRO, Université de Montréal 

4

Traffic grooming in optical WDM mesh networks consists of to packing low-rate connections effectively onto high-rate lightpaths, which, in turn, are established on wavelength links. We investigate a cost vs. GoS benefit analysis of using rerouting in order to improve the network throughput under a dynamic traffic model. We propose two heuristic and one exact rerouting schemes. Simulation results show that rerouting reduces the connection blocking probability significantly, although beyond a given disruption level, the throughput gain becomes very small in regards of the disruption user annoyance.

Multiple Mm-Wave Signal Generation and Transmission in Radio-over-Fiber Systems

M. Mohamed, Departement of Electrical and Computer Engineering, Concordia Univiversity

B. Hraimela, Polygrames Research Group, Ecole Polytechnique

J. X. Zhang, Departement of Electrical and Computer Engineering, Concordia Univiversity

5

Photonic millimeter-wave (mm-wave) generation using optical frequency multiplication (OFM) is considered as a cost-effective solution for radio-over-fiber (RoF) systems. In this work, we comprehensively investigate the generation of multiple mm-wave signals using high-order harmonic generation with a dual-electrode Mach-Zehnder modulator (DE-MZM). In the proposed technique one laser source is used to generate two linearly polarized and orthogonal light waves. Each light-wave is separated and modulated with different DE-MZM which is driven by different set of RF signals. Each DE-MZM is biased at maximum transmission to generate even-order optical sidebands. In this technique, the channel spacing is reduced and inter-symbol-interference is avoided between the generated multiple mm-wave signals. As an example, we consider two RF signals at 7.5 GHz and 8.125 GHz, which carries the data signal and each drives one DE-MZM; and a mm-wave signal at 30 GHz and 32.5GHz, i.e. a frequency quadrupler, is obtained. The performance of the system has been evaluated in terms of receiver sensitivity and Q-factor. Simulation results show that data signal at 625Mb/s is successfully transmitted over 50 km of single mode fiber. The generated mm-wave signal is robust to chromatic dispersion.

A dual Metaheuristic Solution to the Min-RWA Problem

Daniel O’Brien, Département de Génie Électrique, Ecole de Technologie Supérieure

Benoît Châtelain, Département de Génie Électrique, Ecole de Technologie Supérieure

François Gagnon, Département de Génie Électrique, Ecole de Technologie Supérieure

Christine Tremblay, Département de Génie Électrique, Ecole de Technologie Supérieure

Michel P. Bélanger, Nortel

Éric Bernier, Nortel

6

A new routing and wavelength assignment (RWA) algorithm for all-optical networks is introduced.  A genetic algorithm, minimizing the network’s link congestion, is combined with tabu search.  Optimal solutions are found for nearly all test cases.  Compared to reference algorithms and theoretical bounds, the proposed dual metaheuristic approach proved to be more performing than existing methods, most often attaining theoretical bounds.

Optimal Network Capacity Allocation in Service Overlay Networks

Lam Ngok, Dept. Electrical and Computer Engineering , McGill University

Lorne Mason, Dept. Electrical and Computer Engineering , McGill University

7

We study the capacity allocation problem in service overlay networks (SON) with state-dependent connection routing based on revenue maximization. We formulate the dimensioning problem as a profit maximization problem and propose a novel model with several new features. In particular the proposed methodology employs an efficient approximation for state dependent routing that reduces the cardinality of the problem. Moreover, the new formulation also takes into account a more flexible formulation of paths than previous works.

Active Monitoring of All-Optical Networks

Yvan Pointurier, Dept. Electrical and Computer Engineering , McGill University

Mark Coates, Dept. Electrical and Computer Engineering , McGill University

Michael Rabbat, Dept. Electrical and Computer Engineering , McGill University

8

We show that it possible to decrease the amount of hardware needed to monitor the Quality of Transmission (QoT) of lightpaths in all-optical networks by establishing carefully selected ``active lightpaths'', without sacrificing estimation accuracy.  The QoT of lightpaths that are not directly measured by monitoring equipment is estimated with the help of additional ``active lightpaths''.  We gain extra information about the unobserved lightpaths by measuring the QoT of the carefully chosen active lightpaths, which are activated solely for the purpose of monitoring.

Insights in Using Availability-Aware Design for p-Cycle and FIPP Based Networks

Amin Ranjbar, CIISE, Concordia University

Chadi Assi, CIISE, Concordia University

9

Failure-Independent Path-Protecting (FIPP) p-cycle is an extension of the basic p-cycle and an alternative approach for providing fully pre-connected protection paths with end-to-end failure-independent path protection property. We study the unavailability of end-to-end traffic in FIPP based mesh networks, which are designed to protect against single failures and present an availability-aware network design method. Our design method aims at allocating FIPP p-cycles such that the end-to-end unavailability of the protected demands is bounded by an upper limit and the upper limit can be varied as desired. Our study will also focus on determining whether FIPP p-cycles will maintain their resource efficiency advantages over span p-cycles when the network design is based on limiting the unavailability. Our results first show that the length of the FIPP p-cycle plays a vital role in determining the availability of the working path(s). Similar to span p-cycles, higher service working path(s) availability is obtained when the FIPP p-cycle(s) contains fewer hops. Results also indicate the important role of the number of demands protected by the same FIPP p-cycle. We notice that the higher the desired availability is, the less efficient FIPP method becomes. This is due to the fact that in order to achieve higher service availability, the design will limit the number of demands sharing the same FIPP cycle. Accordingly, we affirm that when the network design limits the service unavailability, FIPP tends to be less efficient and its redundancy is 8-13% more than basic p-cycle. Additionally, we observe that when we do not limit the unavailability, the average availability for span p-cycle tends to be more than the FIPP p-cycle method. We present our analysis and discussions on these findings.

Revisiting p-cycles / FIPP p-cycles vs. Shared Link / Path Protection

Caroline Rocha, DIRO, Université de Montréal

Brigitte Jaumard, CIISE, Concordia University

10

While the advantages of p-cycles and FIPP p-cycles are well established, there is no systematic analysis of much bandwidth they consume in comparison of the shared link or path protection schemes. It was also recently observed that, even when enumerating a huge number of cycles, it is difficult to assess on the quality of the solutions provided by ILP models without using specialized tools for large scale programming such as, e.g., column generation techniques. Indeed, using those techniques allows a reduction of up to 37 % of the cost of the solution for FIPP p-cycles. We propose here to investigate the bandwidth protection costs of p-cycles and FIPP p-cycles in comparison of those of shared link and path protection, using column generation techniques for modeling all four protection schemes, and therefore obtaining the optimal values for all of them, out of any doubt. It is then observed that the average excess bandwidth required by p-cycles is about 6.6 % and the one of FIPP p-cycles is 13.4 %.

Efficient and Scalable Design of Protected Working Capacity Envelope

Samir Sebbah, ECE, Concordia University

Brigitte Jaumard, GERAD & CIRRELT, CIISE, Concordia University

11

The PWCE concept was proposed by Grover (2004) in order to simplify network and operation management in survivable WDM networks, assuming protection is handled by p-cycles. The concept also applies for all (shared) protection schemes, i.e., link or segment protection. In this paper, we focus on PCWE with {\pcycles} and investigate a new design method, highly efficient and scalable, for computing the Protected Working Capacity Envelope (PWCE) of a WDM mesh network. Traditional methods proceed in two steps: A first step where a large (sometimes huge) number of cycles is enumerated and a second step where the selection of the most promising p-cycles is made with the help of combinatorial optimization tools. We develop a new (single step) method based on large scale optimization tools, namely column generation techniques, where the generation of cycles is dynamic and embedded within the optimization process. The key advantage of column generation (CG) techniques is that no a-priori cycle enumeration step is required ahead of the optimization process: the generation of the relevant cycles, only one or few at a time, is embedded in the optimization process.
We conducted intensive computational experiments. Not only do we consider several network instances with quite different topology characteristics, but we also compare our CG model and solution method with several existing models and methods in the literature.  Results obtained in the experiments on 5 different network instances, show that the CG model and method outperform by far the results of all previous studies, both with respect to the scalability (much smaller computing times) but also with respect to the quality of the solutions.

Brigitte Jaumard, CIISE, Concordia University

François Vanderbeck, Université de Bordeaux

Benoit Vignac, DIRO, Université de Montréal 

12

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 different mathematical formulations that exploit the decomposability of the problem. We discuss their advantages and disadvantages in terms of solution easiness and fast convergence to an optimal or near optimal solution.