Rerouting Schemes for Dynamic Traffic Grooming in Optical WDM Mesh Networks

Traffic grooming in optical WDM mesh networks is a two-layer routing problem to effectively pack low-rate connections onto high-rate lightpaths, which, in turn, are established on wavelength links. In this work, we employ the rerouting approach to improve the network throughput under the dynamic traffic model. We propose two rerouting schemes, rerouting at lightpath level (RRAL) and rerouting at connection level (RRAC). A qualitative comparison is made between RRAL and RRAC. We also propose the critical-wavelength-avoiding one-lightpath-limited (CWA-1L) and critical-lightpath-avoiding one-connection-limited (CLA-1C) rerouting heuristics, which are based on the two rerouting schemes respectively. Simulation results show that rerouting reduces the connection blocking probability significantly.

An Efficient Scheduling Scheme For On-Demand Lightpath Reservations In Reconfigurable WDM Optical Networks

We propose an efficient scheduling scheme that optimizes advance-reserved lightpath services in reconfigurable WDM networks. A re-optimization approach is devised to reallocate network resources for dynamic service demands while keeping determined schedule unchanged.

Maximizing Resource Sharing in WDM Mesh Networks With Path-Based Protection and Sparse OEO Regeneration

We propose a resource-sharing scheme that supports three kinds of sharing scenarios in a WDM mesh network with path-based protection and sparse OEO regeneration. Several approaches are used to maximize the sharing of wavelength-links and OEO regenerators.

An Analytical Model for Virtual Topology Reconfiguration in Optical Networks and A Case Study

An analytical model for Virtual Topology Reconfiguration (VTR) in optical networks is developed. It aims at the optical networks with a circuit-based data plane and an IPlike control plane. By identifying and analyzing the important factors impacting the network performance due to VTR operations on both planes, we can compare the benefits and penalties of different VTR algorithms and policies. The best VTR scenario can be adaptively chosen from a set of such algorithms and policies according to the real-time network situations. For this purpose, a cost model integrating all these factors is created to provide a comparison criterion independent of any specific VTR algorithm and policy. A case study based on simulation experiments is conducted to illustrate the application of our models.

Dynamic Routing in Translucent WDM Optical Networks

Translucent WDM optical networks use sparse placement of regenerators to overcome the impairments and wavelength contention introduced by fully transparent networks, and achieve a performance close to fully opaque networks with much less cost. Our previous study proved the feasibility of translucent networks using sparse regeneration technique. We addressed the placement of regenerators based on static schemes allowing only fixed number of regenerators at fixed locations. This paper furthers the study by proposing a suite of dynamical routing schemes. Dynamic allocation, advertisement and discovery of regeneration resources are proposed to support sharing transmitters and receivers between regeneration and access functions. This study follows the current trend in optical networking industry by utilizing extension of IP control protocols. Dynamic routing algorithms, aware of current regeneration resources and link states, are designed to smartly route the connection requests under quality constraints. A hierarchical network model, supported by the MPLS-based control plane, is also proposed to provide scalability. Experiments show that network performance is improved without placement of extra regenerators.

Dynamic traffic grooming algorithms for reconfigurable SONET over WDM networks

The emergence of Wavelength Division Multiplexing (WDM) technology provides the capability for increasing the bandwidth of Synchronous Optical Network (SONET) rings by grooming low-speed traffic streams onto different high-speed wavelength channels. Since the cost of SONET add-drop multiplexers (SADM) at each node dominates the total cost of these networks, how to assign the wavelength, groom in the traffic and bypass the traffic through the intermediate nodes has received a lot of attention from researchers recently.

Optimization of Amplifier Placements in Switch-Based Optical Networks

Wavelength division multiplexing (WDM) offers a solution to the problem of exploiting the large bandwidth on optical links; it is the current favorite multiplexing technology for optical communication networks. Due to the high cost of an optical amplifier, it is desirable to strategically place the amplifiers throughout the network in a way that guarantees that all the signals are adequately amplified while minimizing the total number amplifiers being used. Previous studies all consider a star-based network. This paper demonstrates an original approach for solving the problem in switch-based WDM optical network assuming the traffic matrix is always the permutation of the nodes. First we formulate the problem by choosing typical permutations which can maximize traffic load on individual links; then a GA (Genetic Algorithm) is used to search for feasible amplifier placements. Finally, by setting up all the lightpaths without violating the power constaints we confirm the feasibility of the solution.

Performance Analysis of Sparse Traffic Grooming in WDM Mesh Networks

Sparse traffic grooming is a practical problem to be addressed in heterogeneous multi-vendor optical WDM networks where only some of the optical cross-connects (OXCs) have grooming capabilities. Such a network is called as a sparse grooming network. The sparse grooming problem under dynamic traffic in optical WDM mesh networks is a relatively unexplored problem. In this work, we propose the maximize-lightpath-sharing multi-hop (MLS-MH) grooming algorithm to support dynamic traffic grooming in sparse grooming networks. We also present an analytical model to evaluate the blocking performance of the MLS-MH algorithm. Simulation results show that MLSMH outperforms an existing grooming algorithm, the shortest path single-hop (SPSH) algorithm. The numerical results from analysis show that it matches closely with the simulation. The effect of the number of grooming nodes in the network on the blocking performance is also analyzed.

Active Learning to Maximize Area Under the ROC Curve

In active learning, a machine learning algorithmis given an unlabeled set of examples U, and is allowed to request labels for a relatively small subset of U to use for training. The goal is then to judiciously choose which examples in U to have labeled in order to optimize some performance criterion, e.g. classification accuracy. We study how active learning affects AUC. We examine two existing algorithms from the literature and present our own active learning algorithms designed to maximize the AUC of the hypothesis. One of our algorithms was consistently the top performer, and Closest Sampling from the literature often came in second behind it. When good posterior probability estimates were available, our heuristics were by far the best.

An Empirical Study of Fault Localization for End-User Programmers

End users develop more software than any other group of programmers, using software authoring devices such as e-mail filtering editors, by-demonstration macro builders, and spreadsheet environments. Despite this, there has been little research on finding ways to help these programmers with the dependability of their software. We have been addressing this problem in several ways, one of which includes supporting end-user debugging activities through fault localization techniques. This paper presents the results of an empirical study conducted in an end-user programming environment to examine the impact of two separate factors in fault localization techniques that affect technique effectiveness. Our results shed new insights into fault localization techniques for end-user programmers and the factors that affect them, with significant implications for the evaluation of those techniques.

Directed Test Suite Augmentation

As software evolves, engineers use regression testing to evaluate its fitness for release. Such testing typically begins with existing test cases, and many techniques have been proposed for reusing these cost-effectively. After reusing test cases, however, it is also important to consider code or behavior that has not been exercised by existing test cases and generate new test cases to validate these. This process is known as test suite augmentation. In this paper we present a directed test suite augmentation technique, that utilizes results from reuse of existing test cases together with an incremental concolic testing algorithm to augment test suites so that they are coverage-adequate for a modified program. We present results of an empirical study examining the effectiveness of our approach.

Bandit-Based Algorithms for Budgeted Learning

We explore the problem of budgeted machine learning, in which the learning algorithm has free access to the training examples’ labels but has to pay for each attribute that is specified. This learning model is appropriate in many areas, including medical applications. We present new algorithms for choosing which attributes to purchase of which examples in the budgeted learning model based on algorithms for the multi-armed bandit problem. All of our approaches outperformed the current state of the art. Furthermore, we present a new means for selecting an example to purchase after the attribute is selected, instead of selecting an example uniformly at random, which is typically done. Our new example selection method improved performance of all the algorithms we tested, both ours and those in the literature.

Sofya: Supporting Rapid Development of Dynamic Program Analyses for Java

Dynamic analysis is an increasingly important means of supporting software validation and maintenance. To date, developers of dynamic analyses have used low-level instrumentation and debug interfaces to realize their analyses. Many dynamic analyses, however, share multiple common high-level requirements, e.g., capture of program data state as well as events, and efficient and accurate event capture in the presence of threading. We present SOFYA – an infra-structure designed to provide high-level, efficient, concurrency-aware support for building analyses that reason about rich observations of program data and events. It provides a layered, modular architecture, which has been successfully used to rapidly develop and evaluate a variety of demanding dynamic program analyses. In this paper, we describe the SOFYA framework, the challenges it addresses, and survey several such analyses.

Predicting Accurate and Actionable Static Analysis Warnings: An Experimental Approach

Static analysis tools report software defects that may or may not be detected by other verification methods. Two challenges complicating the adoption of these tools are spurious false positive warnings and legitimate warnings that are not acted on. This paper reports automated support to help address these challenges using logistic regression models that predict the foregoing types of warnings from signals in the warnings and implicated code. Because examining many potential signaling factors in large software development settings can be expensive, we use a screening methodology to quickly discard factors with low predictive power and cost-effectively build predictive models. Our empirical evaluation indicates that these models can achieve high accuracy in predicting accurate and actionable static analysis warnings, and suggests that the models are competitive with alternative models built without screening.

Infrastructure Support for Controlled Experimentation with Software Testing and Regression Testing Techniques

Where the creation, understanding, and assessment of software testing and regression testing techniques are concerned, controlled experimentation is an indispensable research methodology. Obtaining the infrastructure necessary to support such experimentation, however, is difficult and expensive. As a result, progress in experimentation with testing techniques has been slow, and empirical data on the costs and effectiveness of techniques remains relatively scarce. To help address this problem, we have been designing and constructing infrastructure to support controlled experimentation with testing and regression testing techniques. This paper reports on the challenges faced by researchers experimenting with testing techniques, including those that inform the design of our infrastructure. The paper then describes the infrastructure that we are creating in response to these challenges, and that we are now making available to other researchers, and discusses the impact that this infrastructure has and can be expected to have.