The rapid expansion of 5G and the upcoming arrival of 6G have significantly increased the demand for cloud computing resources, especially in edge cloud servers, to meet stringent connectivity and latency requirements. This surge has raised serious energy concerns as data centers now account for about 1–1.5% of global energy consumption and contribute about 1% of global CO 2 emissions. In response to these facts, this study proposes a novel energy-aware machine learning model, using power sensor data from physical machines (PMs) in data centers, to optimize energy consumption while managing container placement as a use case. We conducted experiments in a testbed using realistic 5G traffic scenarios, deliberately avoiding artificial stressors such as stress-ng, which create synthetic loads that do not accurately reflect real-world resource utilization. Our machine learning model, particularly the XGBoost implementation, proved to be highly effective, achieving an R 2 score of 91.2%. The model demonstrated the ability to reduce energy consumption by 3% and improve task completion times, all without the need for explicit consolidation strategies or cluster reconfiguration. This approach highlights the power of machine learning in optimizing energy efficiency in dynamic and resource-intensive environments such as edge cloud servers, providing a scalable solution for data centers facing increasing energy demands.

Ensuring the highest levels of performance and reliability for customized services in fifth-generation (5G) and beyond (B5G) networks requires the automation of resource management within network slices. In this paper, we propose PCLANSA, a proactive closed-loop algorithm that dynamically allocates and scales resources to meet the demands of diverse applications in real time for an end-to-end (E2E) network slice. In our experiment, PCLANSA was evaluated to ensure that each virtual network function is allocated the resources it requires, thereby maximizing efficiency and minimizing waste. This goal is achieved through the intelligent scaling of virtual network functions. The benefits of PCLANSA have been demonstrated across various network slice types, including eMBB, mMTC, uRLLC, and VoIP. This finding indicates the potential for substantial gains in resource utilization and cost savings, with the possibility of reducing over-provisioning by up to 54.85%.

The challenge of handling missing data in time series is critical for maintaining the accuracy and reliability of machine learning (ML) models in applications like fifth generation mobile communication (5G) network management. Traditional methods for validating imputation rely on ground truth data, which is inherently unavailable. This paper addresses this limitation by introducing two statistical metrics, the wasserstein distance (WD) and jensen-shannon divergence (JSD), to evaluate imputation quality without requiring ground truth. These metrics assess the alignment between the distributions of imputed and original data, providing a robust method for evaluating imputation performance based on internal structure and data consistency. We apply and test these metrics across several imputation techniques. Results demonstrate that WD and JSD are effective metrics for assessing the quality of missing data imputation, particularly in scenarios where ground truth data is unavailable.

We propose a first Asynchronous Federated Split Learning (AFSL), to add the flexibility of asynchronous computing to the combination of federated and split learning. This amounts to designing a harmonious combination of different paradigms in order to benefit from the advantages of each of them and to reduce the impacts of their shortcomings.This way, AFSL answers to the increasingly rising interest for distributed algorithms with the advent of edge computing in order to support new market segments, such as cloud gaming, immersive eXtended Reality (XR), indoor positioning, and mission critical IoT networks, with stringent requirements on latency and reliability.Computational experiments are conducted on IID and non-IID datasets to investigate the added value of the asynchronous feature. Results indicate that AFSL can accelerate model learning by up to 86% without sacrificing the model’s convergence and accuracy. Indeed, not only average training times are reduced, but clients use fewer resources, a critical characteristic for devices with limited computing capabilities, e.g., in edge devices. Performance degradation can be mitigated by a careful selection of the aggregation principle. Other advantages are with AFSL training in dynamic scenarios as it provides robustness with a short recovery time by leveraging asynchronous client training.

Cloud data centers (DCs) consume large amounts of energy and contribute significantly to environmental concerns. Furthermore, with the advent of 5G and B5G networks, increasingly software-oriented and becoming highly dependent on cloud computing, it becomes imperative to optimize their energy consumption. Thus, in this study, we present a virtual machine placement algorithm that minimizes the energy consumption of a cluster of server machines. Our solution is embodied through the use of sensors embedded inside physical server machines, enabling the introduction of new features for sensitive thermal awareness and proactive hot spot avoidance. Leveraging this significantly enhanced feature space, we implement data-driven predictive machine learning models along with a heuristic placement algorithm (CPP), enabling proactive VM placements that are both energy-aware and thermal-aware. Indeed, experiments carried out on a cluster of physical server machines demonstrate high performance by both the ML models and the placement algorithm (CPP). Compared with the best baseline algorithm, our solution reduced power consumption and temperature by 7% and 2%, respectively, while avoiding hot spots and maintaining efficient load distribution, thereby reducing the overhead of physical machines by 28%.

We study the dynamic joint service function chain (SFC) embedding problem in a network function virtualization (NFV)-enabled edge cloud network. Our design goal is to optimize the network throughput by maximizing the average number of SFCs successfully embedded into the network, i.e., the Grade of Service (GoS), while guaranteeing their individual stringent end-to-end delay and resource constraints over a time horizon. To this end, we proposed a deep reinforcement learning (DRL)-based framework for jointly performing VNF embedding and routing tasks for the arrival SFCs in the considered NFV-enabled network. We implemented two versions of the proposed framework, one with the Deep Q-learning (DQL) method and one with the Advantage Actor-Critic (A2C) as the core algorithms, respectively. Moreover, for training these DRL algorithms and demonstrating the performance of the proposed framework, we implement a network environment based on the real-world network topology and a service request generator for generating SFCs traffic. Numerical results show that the DQL and A2C versions of the proposed framework achieve over 95% of the average GoS and over 95% of the network throughput ratio compared to the upper bound. This performance level is comparable to that of the near-optimal optimization-based approach while having ten times shorter execution times.

Automated resource management for 5G network slicing implies the need to assign each slice the necessary resources, i.e., the ability to predict their respective requests and resource requirements. Machine learning models and algorithms can meet these needs provided the required data is available. Unfortunately, 5G traffic data remains sparse despite many studies relying on machine learning models and algorithms for traffic forecasting or automated network resource management. In this study, we introduce a 5G-type predictable traffic generator that relies on the refactoring of open data of vehicle and pedestrian traffic from the City of Montreal. Indeed, the latter data is refactored in order to generate different classes of network traffic, with different characteristics associated with typical 5G applications, and then with different traffic patterns and peak hours. The result is a valuable traffic generation tool for researchers interested in validating machine learning algorithms aimed at, for example, traffic forecasting, resource elasticity, or automated scaling of slice resources.

During the COVID-19 pandemic, social distancing has been applied worldwide to reduce the risk of infection. In hospitals, this requires a new strategy for movement management in the corridors to avoid cross-overs and satisfy social distancing requirements. In this paper, we study the problem of routing and path finding for two flows of patients (COVID-19 and Non-COVID) in the hospital during the pandemic using as many disjoint paths as possible. We present two scenarios based respectively on an offline and an online method to model the routing and labeling of the hospital paths and compare them using a simulation tool. The simulation result shows the proposed solutions outperform the baseline which is based on the Dijkstra algorithm. This outcome can help increase safety by considering the guideline for COVID-19 and Non-COVID patients in healthcare centers during the pandemic.

With the 5th generation of mobile networking (5G) on our doorstep, optical network operators are reorganizing their network infrastructure to deploy different topologies (virtual networks/applications) on the same network infrastructure on demand. This new paradigm, called network slicing, can be enabled by segmenting the network resources based on the requirements of the application level. This paper investigates a nested decomposition mathematical modeling to design a reliable 5G network slicing problem, i.e., every virtual path is protected against any single link failures by a dedicated backup disjoint virtual path. This new modeling revises and improves some previously proposed decomposition models. Then, we propose a column generation algorithm to solve the new modeling exactly. Moreover, this paper provides the computation of dual bounds with Lagrangian relaxation to assess the solutions’ accuracy that many existing nested-decomposition applications have omitted. Extensive computational results show that we can get$\varepsilon $-optimal reliable 5G slicing solutions with small$\varepsilon $(about 2% on average) in fairly reasonable computational times. In addition, we also propose several acceleration schemes using parallel programming to reduce computational time. The experimental results show that the slice-based scheme outperforms the path-based one in terms of parallelism.

We design an effective and scalable Deep Reinforcement Learning (DRL) approach for the Routing, Modulation and Spectrum Assignment (RMSA) problem in elastic optical networks. We use Convolutional Neural Networks (CNN) to embed the state and Deep Neural Networks (DNN) to learn the policy. We propose a novel state representation and reward function that interestingly guide the agent on assigning appropriate routes and spectrum by incorporating information on the spectrum utilisation and spectrum fragmentation. This gives the agent information about the consequence or cost of each action across the network, reducing the level of knowledge abstraction required for the agent. To show the effectiveness of the reward function and the importance of well-designed state representations, we have designed two state representations: the first with aggregation of spectrum occupancy information and the second without aggregation. The Proximal Policy Optimization (PPO) algorithm is investigated with an actor critic model where an entropy bonus is added to the loss function to ensure sufficient exploration. The proposed solution is compared with a greedy heuristic and a PPO with standard reward and state representation. Numerical results show that the proposed model provides very good solutions and works well on dataset instances with large topologies (up to 75 nodes). The proposed PPO outperformed the baseline algorithms by obtaining the largest throughput on all test instances. In addition, its spectrum usage has the lowest fragmentation.

The Open Radio Access Network (O-RAN) architecture brings openness, intelligence, and virtualization to RANs, allowing multi-vendor existence, achieving economics of scale, and enabling intelligent management and orchestration. O-RAN components such as near real-time RAN Intelligent Controllers (RICs), O-RAN Central Units (O-CUs), and O-RAN Distributed Unit (O-DUs) can be considered as virtual network functions hosted on the O-Cloud. This virtualization allows network service providers to disaggregate O-RAN functions from their hard-ware, enabling dynamic instantiation of services and reducing their capital and operating costs. However, with openness and virtualization, availability guarantees become more difficult to maintain as the network is now prone to both software and hardware failures. In this paper, we investigate a decomposition model for the design of reliable 0-RAN deployment under a dedicated virtual network function (VNF)-protection scheme. The proposed model maximizes the network's yearly availability by providing a placement decision for all 0-RAN VNFs and their backup instances. The model is solved by a column generation algorithm making it a scalable algorithm for large-scale 0-RAN deployments. Extensive computational results show that the algorithm can produce ε-optimal solutions with negligible ε (less than 0.1%) in reasonable computational times. These results significantly enlarge the exact solutions of the state-of-the-art algorithms for this problem.

Current 5G and beyond research explores how to leverage network virtualization, which allows network operators to partition the network into multiple independent slices, each of which can carry multiple types of traffic, to provide flexibility and scalability in the deployment of new network services. In this context, this paper presents the description of a network simulator, that addresses the key related 5G features, i.e., modeling of virtual network functions, network slicing, ability to change some network parameters during run-time, and a more realistic network traffic generation. During the demo, we deploy several slices with different types of traffic to demonstrate that our simulator can support applications like network management and orchestration. The evaluation results show that our simulator is a powerful tool for testing 5G networks.

Road accidents have a high societal cost that could be reduced through improved risk predictions using machine learning. This study investigates whether telemetric data collected on long-distance trucks can be used to predict the risk of accidents associated with a driver. We use a dataset provided by a truck transportation company containing the driving data of 1,141 drivers for 18 months. We evaluate two different machine learning approaches to perform this task. In the first approach, features are extracted from the time series data using the FRESH algorithm and then used to estimate the risk using Random Forests. In the second approach, we use a convolutional neural network to directly estimate the risk from the time series data. We find that neither approach is able to successfully estimate the risk of accidents on this dataset, in spite of many methodological attempts. We discuss the difficulties of using telemetric data for the estimation of the risk of accidents that could explain this negative result.

Information systems such as cellular networks produce large volumes of data, making the characterization of network faults a difficult task. In this work, we introduce a new fault analysis framework based on association rule mining and validate it to identify the root cause of faults in information systems. The paper describes a strategy using association rules to specifically target faults while improving runtime performance relative to the standard Apache Spark implementation. We also introduce a novel association rule filtering strategy called Cover Set filtering that prunes and merges rule sets to produce high-quality, concise and interpretable results. The proposed framework is evaluated with real-world telecommunication datasets. Comparing this framework approach with other strategies, we demonstrate a better rule diversity in general and a sufficiently compact analysis of the faults. The validation of our experimental results was conducted by telecommunications experts, who confirmed the clarity and value of the results for a quantitative assessment of cellular network failures.

Survivability is an important component in the requirements in elastic optical networks (EONs) with virtualization. In this paper, we examine the significance of network survivability design against single-link failure under dedicated protection and bandwidth squeezing schemes under multiple virtual topologies. We proposed an integer linear programming (ILP) formulation and a genetic algorithm (GA) to derive some different types of protection for each virtual topology considering routing and a channel-based spectrum approach. The proposed ILP and GA provide efficient survivability results and resource savings (in terms of spectrum) for a full design of modern virtualized EONs with different kinds of mechanisms for protection.

Abstract Modern 5G networks promise more bandwidth, less delay and more flexibility for an ever increasing number of users and applications, with Software Defined Networking, Network Function Virtualization and Network Slicing as key enablers. Within that context, efficiently provisioning the network and cloud resources of a wide variety of applications with dynamic user demand is a real challenge. We study here the network slice reconfiguration problem. Reconfiguring network slices from time to time reduces network operational costs and increases the number of slices that can be managed within the network. However, this affect the Quality of Service of users during the reconfiguration step. To solve this issue, we study solutions implementing a make-before-break scheme. We propose new models and scalable algorithms (relying on column generation techniques) that solve large data instances in few seconds.

Optical multilayer optimization periodically reorganizes layer 0-1-2 network elements to handle both existing and dynamic traffic requirements in the most efficient manner. This delays the need for adding new resources in order to cope with the evolution of the traffic, thus saving CAPEX. The focus of this paper is on Layer 2, i.e., on capacity reoptimization at the optical transport network (OTN) layer when routes (e.g., LSPs in MPLS networks) are making unnecessarily long detours to evade congestion. Reconfiguration into optimized routes can be achieved by re-defining the routes, one at a time, so that they use the vacant resources generated by the disappearance of services using part of a path that transits the congested section. To maintain the Quality of Service, it is desirable to operate under a Make-Before-Break (MBB) paradigm, with the minimum number of reroutings. The challenge is to determine the best rerouting order while minimizing the bandwidth requirement. We propose an exact and scalable optimization model for computing a minimum bandwidth rerouting scheme subject to MBB in the OTN layer of an optical network. Numerical results show that we can successfully apply it on networks with up to 30 nodes, a very significant improvement with respect to the state of the art. We also provide some reoptimization analysis in terms of the bandwidth requirement vs. the number of reroutings.

Modern 5G networks promise more bandwidth, less delay, and more flexibility for an ever increasing number of users and applications, with Software Defined Networking, Network Function Virtualization, and Network Slicing as key enablers. Within that context, efficiently provisioning network and cloud resources of a wide variety of applications with dynamic users' demands is a real challenge. In this work, we consider the problem of network slice reconfiguration. Reconfiguring from time to time network slices allows to reduce the network operational costs and to increase the number of slices that can be managed within the network. However, it impacts users' Quality of Service during the reconfiguration step. To solve this issue, we study solutions implementing a make-before-break scheme. We propose new models and scalable algorithms (relying on column generation techniques) that solve large data instances in few seconds.

Road accidents are an important issue of our modern societies, responsible for millions of deaths and injuries every year in the world. In Quebec only, in 2018, road accidents are responsible for 359 deaths and 33 thousands of injuries. In this paper, we show how one can leverage open datasets of a city like Montreal, Canada, to create high-resolution accident prediction models, using big data analytics. Compared to other studies in road accident prediction, we have a much higher prediction resolution, i.e., our models predict the occurrence of an accident within an hour, on road segments defined by intersections. Such models could be used in the context of road accident prevention, but also to identify key factors that can lead to a road accident, and consequently, help elaborate new policies. We tested various machine learning methods to deal with the severe class imbalance inherent to accident prediction problems. In particular, we implemented the Balanced Random Forest algorithm, a variant of the Random Forest machine learning algorithm in Apache Spark. Interestingly, we found that in our case, Balanced Random Forest does not perform significantly better than Random Forest. Experimental results show that 85% of road vehicle collisions are detected by our model with a false positive rate of 13%. The examples identified as positive are likely to correspond to high risk situations. In addition, we identify the most important predictors of vehicle collisions for the area of Montreal: the count of accidents on the same road segment during previous years, the temperature, the day of the year, the hour and the visibility.

In the context of multi-agent systems, Automated Mechanism Design (AMD) is the computer-based design of the rules of a mechanism, which reaches an equilibrium despite the fact that agents can be selfish and lie about their preferences. Although it has been shown that AMD can be modelled as a linear program, it is with an exponential number of variables and consequently, there is no known efficient algorithm. We revisit the latter linear program model proposed for the AMD problem and introduce a new one with a polynomial number of variables. We show that the latter model corresponds to a Dantzig-Wolfe decomposition of the second one and design efficient solution schemes in polynomial time for both two models. Numerical experiments compare the solution efficiency of both models and show that we can solve very significantly larger data instances than before, up to 2,000 agents or 2,000 resources in about 35 seconds.

We aim to predict and explain service failures in supply-chain networks, more precisely among last-mile pickup and delivery services to customers. We analyze a dataset of 500,000 services using (1) supervised classification with Random Forests, and (2) Association Rules. Our classifier reaches an average sensitivity of 0.7 and an average specificity of 0.7 for the 5 studied types of failure. Association Rules reassert the importance of confirmation calls to prevent failures due to customers not at home, show the importance of the time window size, slack time, and geographical location of the customer for the other failure types, and highlight the effect of the retailer company on several failure types. To reduce the occurrence of service failures, our data models could be coupled to optimizers, or used to define counter-measures to be taken by human dispatchers.

Optical multilayer optimization continuously reorganizes layer 0-1-2 network elements to handle both existing and dynamic traffic requirements in the most efficient manner. This delays the need to add new resources for new requests, saving CAPEX and leads to optical network defragmentation. The focus of this paper is on Layer 2, i.e., on capacity defragmentation at the OTN layer when routes (e.g., LSPs in MPLS networks) are making unnecessarily long detours to evade congestion. Reconfiguration into optimized routes can be achieved by re-defining the routes, one at a time, so that they use the vacant resources generated by the disappearance of services using part of a path that transits the congested section. For the Quality of Service, it is desirable to operate under Make Before Break (MBB), with the minimum number of rerouting. The challenge is to identify the rerouting order, one connection at a time, while minimizing the bandwidth requirement. We propose an exact and scalable optimization model for computing a minimum bandwidth rerouting scheme subject to MBB in the OTN layer of an optical network. Numerical results show that we can successfully apply it on networks with up to 30 nodes, a very significant improvement with the state of the art. We also provide some defragmentation analysis in terms of the bandwidth requirement vs. the number of reroutings.

In the context of Software-Defined Networks (SDN), Network Function Virtualization (NFV) is a new network paradigm in which network functions are implemented in software as Virtual Network Functions (VNFs). To meet the demand, VNFs are next interconnected to form different complete end-to-end services, also known as a Service Function Chains (SFCs). We study the problem of deploying reliable Service Function Chains over a virtualized network function architecture. While there is a need for reliable service function chaining, there is a high cost to pay for it in terms of bandwidth and VNF processing requirements. We investigate two different protection mechanisms and discuss their resource requirements, as well as the latency of their paths. For each mechanism, we develop a scalable exact mathematical model using column generation.

Network function virtualization (NFV) aims to simplify service deployment using virtual network functions (VNFs). Service deployment involves the placement of VNFs and in-sequence routing of traffic flows through VNFs comprising a service chain (SC). The joint VNF placement and traffic routing is called SC mapping. In a wide-area network (WAN), where several traffic flows, generated by many distributed node pairs, require the same SC; a single instance (or occurrence) of that SC might not be enough. SC mapping with multiple SC instances for same SC is a very complex problem, since sequential traversal of VNFs has to be maintained while accounting for traffic flows in various directions. This paper is the first to deal with the problem of SC mapping with multiple SC instances to minimize network resource consumption. We propose an integer linear program (ILP), a column-generation-based ILP (CG-ILP), and a two-phase column-generation-based model (2PhMod) to solve this problem. ILP does not scale to large networks and CG-ILP scalability is limited by quadratic constraints. So, to get results over large network topologies within reasonable computational times, we propose 2PhMod. Using such an approach, we observe that an appropriate choice of only a small set of SC instances leads to a solution very close to minimum bandwidth consumption. Furthermore, this approach also helps us to analyze effects of number of VNF replicas and number of NFV nodes on bandwidth consumption when deploying these minimum number of SC instances.

Target monitoring is an important ConvergeCast application of wireless sensor networks in which sensors monitor a set of targets, and forward the collected data using multi-hop routing to the same location, called the sink. Nearly all previously proposed models only output a set of link transmission configurations, i.e., sets of links that can simultaneously transmit, without providing an ordering of the transmission configurations, nor guaranteeing that such an ordering exists using only the prescribed number of slots. As such, they do not provide a valid schedule to achieve ConvergeCast, and only give a lower bound on the number of slots required for a schedule. In this paper, we propose a first one phase decomposition model and algorithm that outputs a complete and optimum scheduling, i.e., with the output consisting in an ordered sequence of transmission configurations that achieves ConvergeCast. In addition, we show that the resulting transmission graph is not necessarily a tree. The resulting algorithm provides much better schedules, up to 15% less time slots required, than those of the previous best available mathematical programming or heuristic approaches in the literature.

This paper discusses a unique formulation for the en-route flight planning problem in a constrained airspace with the objective to minimize costs incurred from earliness, lateness, and fuel-consumption, and to ensure flight safety. Mid-air conflict and collision avoidance, and also minimum separation distance between aircraft and speed-dependent fuel-consumption-rate, are explicitly formulated. A 3D mesh network consisting of waypoints is used to provide alternative routing options for aircraft. The formulation of fuel-consumption-rate as a function of speed as part of the air-traffic planning (ATP) problem is unique in the literature. Moreover, this paper is the first attempt to model the mid-air conflict and collision avoidance as part of the ATP problem. In order to demonstrate the capabilities of the mathematical model, test instances were generated and solved by three different solution strategies. The proposed centralized solution strategy can optimally solve small size instances, similar to the air-traffic around airports to help air-traffic control authorities to manage arrival and departure sequences. Larger networks that include several airports can be solved by the proposed two sequential solution strategies (decentralized and hybrid solution strategies) to help air-traffic planning authorities to manage air-traffic safely and more economically.

Network Function Virtualization (NFV) aims to simplify deployment of network services by running Virtual Network Functions (VNFs) on commercial off-the-shelf servers. Service deployment involves placement of VNFs and in-sequence routing of traffic flows through VNFs comprising a Service Chain (SC). The joint VNF placement and traffic routing is usually referred as SC mapping. In a Wide Area Network (WAN), a situation may arise where several traffic flows, generated by many distributed node pairs, require the same SC, one single instance (or occurrence) of that SC might not be enough. SC mapping with multiple SC instances for the same SC turns out to be a very complex problem, since the sequential traversal of VNFs has to be maintained while accounting for traffic flows in various directions. Our study is the first to deal with SC mapping with multiple SC instances to minimize network resource consumption. Exact mathematical modeling of this problem results in a quadratic formulation. We propose a two-phase column-generation-based model and solution in order to get results over large network topologies within reasonable computational times. Using such an approach, we observe that an appropriate choice of only a small set of SC instances can lead to solution very close to the minimum bandwidth consumption.

Software-Defined Networking is a new approach to the design and management of networks. It decouples the software-based control plane from the hardware-based data plane while abstracting the underlying network infrastructure and moving the network intelligence to a centralized software-based controller where network services are deployed. The challenge is then to efficiently provision the service chain requests, while finding the best compromise between the bandwidth requirements, the number of locations for hosting Virtual Network Functions (VNFs), and the number of chain occurrences. We propose two ILP (Integer Linear Programming) models for routing service chain requests, one of them with a decomposition modeling. We conduct extensive numerical experiments, and show we can solve exactly the routing of service chain requests in a few minutes for networks with up to 50 nodes, and traffic requests between all pairs of nodes. We investigate the best compromise between the bandwidth requirements and the number of VNF nodes.

We consider the scheduling problem for Aggregated ConvergeCast in wireless sensor networks with a physical interference model. Previous work consists of either heuristics without performance guarantees, or approximation algorithms which do not perform well in practice. We propose here a first scalable mathematical SINR (Signal to Interference plus Noise Ratio) model that outputs an optimal Aggregated ConvergeCast schedule. We use large scale optimization techniques, namely a Dantzig-Wolfe decomposition algorithm, to solve it. We perform extensive simulations on networks with upto 70 sensors, and compare our results with the best heuristic in the literature using a SINR model. Results show that schedules output by our new model are significantly better than those output by the best available heuristic, i.e., with TDMA frames that are about 50% shorter.

Energy optimization in cellular networks has been studied using different perspectives in the literature: sleep patterns, network interference, association of users and base stations, resource allocation of resources (bandwidth and power), etc. All these means have been discussed individually in previous works. However, none of the existing works has succeeded in proposing an exact mathematical model that takes into account several of these parameters simultaneously. In this article, we propose a first exact modelling of several network parameters and their interaction in order to minimize the energy consumption in a LTE cellular network. The optimization model guarantees to satisfy all the users with a minimum quality of service (data rate). Its exact solution allows energy savings of up to 50% in a moderately loaded network, which leads to energy savings up to twice that of the heuristic proposed by Piunti et al., (2015). Various numerical results are presented on hexagonal and randomly generated cellular networks.

While the routing and wavelength assignment (RWA) has been widely studied, a very few studies attempt to solve realistic size instances, namely, with 100 wavelengths per fiber and a few hundred nodes. Indeed, state of the art is closer to around 20 nodes and 30 wavelengths, regardless of what the authors consider, heuristics or exact methods with a very few exceptions. In this paper, we are interested in reducing the gap between realistic data sets and test bed instances that are often used, using exact methods. Even if exact methods may fail to solve in reasonable time very large instances, they can, however, output a-solutions with a very good and proven accuracy. The novelty of this paper is to exploit the observations that optimal solutions contain a very large number of light paths associated with shortest paths or k-shortest paths with a small k. We propose different RWA algorithms that lead to solve exactly or near exactly much larger instances than in the literature, i.e., with up to 150 wavelengths and 90 nodes. Extensive numerical experiments are conducted on both the static and dynamic incremental planning RWA problem.

We propose a new decomposition model and a multi-column generation algorithm for solving the Locomotive Assignment Problem (LAP). The decomposition scheme relies on consist configurations, where each configuration is made of a set of trains pulled by the same set of locomotives. We use the concept of conflict graphs in order to reduce the number of trains to be considered in each consist configuration generator problem: this contributes to significantly reduce the fraction of the computational times spent in generating new potential consists. In addition, we define a column generation problem for each set of variables, leading to a multi-column generation process, with different types of columns. Numerical results, with different numbers of locomotives, are presented on adapted data sets coming from Canada Pacific Railway (CPR). They show that the newly proposed algorithm is able to solve exactly realistic data instances for a timeline spanning up to 6 weeks, in very reasonable computational times.

Networks built on SDH and SONET have been widely deployed across the globe and a good portion of the metro network data infrastructure continues to rely on these legacy technologies. Most Communications Service Providers (CSPs) expect to operate SONET/SDH infrastructures until the end of the decade, before ultimately migrating to IP-centric, SDN-enabled networks. Such a migration is a major undertaking, which can take several months due to limited maintenance windows and the minimization of outages. Indeed, CSPs need effective optimization algorithms to be able to predict the time and resources required for the migration of large SONET/SDH networks. Under the assumption that the new network is already entirely built before the migration takes place, we present a model that estimates the number of required maintenance windows and technicians in order to perform the migration. Migration is formulated as a circuit migration problem, where each circuit is migrated with careful technician coordination in order to minimize the outages. The proposed model is a planning one, which estimates the cost and duration of a network migration subject to technician availability, outage constraints, and for given maintenance windows. Computational experiences on a Ciena's customer network migration instance complete our study.

We consider a multilayer network design model arising from a real-life telecommunication application where traffic routing decisions imply the installation of expensive nodal equipment. Customer requests come in the form of bandwidth reservations for a given origin destination pair. Bandwidth demands are expressed as multiples of nominal granularities. Each request must be single-path routed. Grooming several requests on the same wavelength and multiplexing wavelengths in the same optical stream allow a more efficient use of network capacity. However, each addition or withdrawal of a request from a wavelength requires optical to electrical conversion and the use of cross-connect equipment with expensive ports of high densities. The objective is to minimize the number of required ports of the cross-connect equipment. We deal with backbone optical networks, therefore with networks with a moderate number of nodes (14 to 20) but thousands of requests. Further difficulties arise from the symmetries in wavelength assignment and traffic loading. Traditional multicommodity network flow approaches are not suited for this problem. Instead, four alternative models relying on Dantzig–Wolfe and/or Benders' decomposition are introduced and compared. The formulations are strengthened using symmetry breaking restrictions, variable domain reduction, zero-one discretization of integer variables, and cutting planes. The resulting dual bounds are compared to the values of primal solutions obtained through hierarchical optimization and rounding procedures. For realistic size instances, our best approaches provide solutions with optimality gap of approximately 5% on average in around 2 h of computing time. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 67(4), 277–298 2016

We aim at dimensioning fixed broadband microwave wireless networks under unreliable channel conditions. As the transport capacity of microwave links is prone to variations due to, e.g., weather conditions, such a dimensioning requires special attention. It can be formulated as the determination of the minimum cost bandwidth assignment of the links in the network for which traffic requirements can be met with high probability, while taking into account that transport link capacities vary depending on channel conditions. The proposed optimization model represents a major step forward since we consider dynamic routing. Experimental results show that the resulting solutions can save up to 45% of the bandwidth cost compared to the case where a bandwidth over-provisioning policy is uniformly applied to all links in the network planning. Comparisons with previous work also show that we can solve much larger instances in significantly shorter computing times, with a comparable level of reliability.

We address the problem of minimizing TDMA frame length in a wireless sensor network charged with monitoring a given set of targets. The problem reduces to finding a minimal set of so-called configurations that delivers data from the targets to a specially designated sink node, where each configuration is a set of links that can transmit concurrently without significant interference. We assume a SINR-based interference model. We use a column generation technique to derive near-optimal solutions even when integrality constraints are enforced on coverage and flow variables. We also introduce a heuristic and a hybrid algorithm to efficiently solve the problem by leveraging a wide range of network parameters related to transmission power control, data rates, and routing. Our results show that significant gains in scalability can be obtained by using our methods.

Optical networks are crucial to support increasingly demanding cloud services. Delivering the requested quality of services (in particular latency) is key to successfully provisioning end-to-end services in clouds. Therefore, as for traditional optical network services, it is of utter importance to guarantee that clouds are resilient to any failure of either network infrastructure (links and/or nodes) or data centers. A crucial concept in establishing cloud services is that of network virtualization: the physical infrastructure is logically partitioned in separate virtual networks. To guarantee end-to-end resilience for cloud services in such a set-up, we need to simultaneously route the services and map the virtual network, in such a way that an alternate routing in case of physical resource failures is always available. Note that combined control of the network and data center resources is exploited, and the anycast routing concept applies: we can choose the data center to provide server resources requested by the customer to optimize resource usage and/or resiliency. This paper investigates the design of scalable optimization models to perform the virtual network mapping resiliently. We compare various resilience options, and analyze their compromise between bandwidth requirements and resiliency quality.

Cloud computing services are emerging as an essential component of the industry ICT infrastructure and, consequently, one of the fastest growing business opportunities for Internet infrastructure and service providers. Many enterprises are moving their services towards cloud infrastructures. In this rapidly growing market, datacenter (DC) scalability is becoming a major technical challenge for service providers as well as its performance optimization, with a key focus on the network technologies and their control. In fact, service providers have to cope with cloud services delivered by more and more geographically distributed DCs, ever increasing requests by users and DC providers for very high throughputs and low latencies, resource dynamicity and elasticity (i.e. flexible storage and computing on demand) and seamless resource/service migration. The future Internet architecture needs to offer:

We address the dimensioning of infrastructure, comprising both network and server resources, for large-scale decentralized distributed systems such as grids or clouds. We design the resulting grid/cloud to be resilient against network link or server failures. To this end, we exploit relocation: Under failure conditions, a grid job or cloud virtual machine may be served at an alternate destination (i.e., different from the one under failure-free conditions). We thus consider grid/cloud requests to have a known origin, but assume a degree of freedom as to where they end up being served, which is the case for grid applications of the bag-of-tasks (BoT) type or hosted virtual machines in the cloud case. We present a generic methodology based on integer linear programming (ILP) that: chooses a given number of sites in a given network topology where to install server infrastructure; and determines the amount of both network and server capacity to cater for both the failure-free scenario and failures of links or nodes. For the latter, we consider either failure-independent (FID) or failure-dependent (FD) recovery. Case studies on European-scale networks show that relocation allows considerable reduction of the total amount of network and server resources, especially in sparse topologies and for higher numbers of server sites. Adopting a failure-dependent backup routing strategy does lead to lower resource dimensions, but only when we adopt relocation (especially for a high number of server sites): Without exploiting relocation, potential savings of FD versus FID are not meaningful.

The efficiency of multi-channel multi-radio wireless mesh networks can be improved with the increase of the number of channels and radios. Despite the availability of up to 11 channels in 802.11, we can choose only up to three non overlapping channels at any given time. In this study, we investigate how to design a channel assignment and a scheduling algorithm, which both exploit partially overlapping channels in order to maximize the throughput. We next examine how much additional throughout we can obtain by doing so, in comparison with only using three orthogonal channels. Numerical experiments show that we can gain up to 25% of throughput by appropriately managing overlapping channels.

Application opportunities associated with video, voice, and data triple-play result in a dramatic demand increase in metro transport networks, with traffic patterns becoming increasingly dynamic and difficult to predict. This is driving the need of core networks with a high degree of flexibility and multigranularities to carry traffic. We propose to investigate the question of what this means in terms of dynamic protection provisioning. In other words, we want to study how stable are the protection structures under dynamic traffic, i.e., how much and how often they need to be updated in a dynamic survivable WDM network. While most studies on the stability of protection structures have been conducted onp-cycles and link shared protection, we propose to investigate here the stability of failure-independent path-protecting (FIPP)p-cycles under dynamic traffic. For doing so, we design and develop an original scalable mathematical model that we solve using large-scale optimization tools. Numerical results show that FIPPp-cycles are remarkably stable under the evaluation of the number of required optical bypass reconfigurations under dynamic traffic.

ABSTRACT In this paper, we propose a cross‐layer design framework for the joint problem of coding‐aware routing and scheduling in WiMAX‐based mesh networks with unicast sessions. The model attempts to maximize the system throughput by exploiting opportunistic coding opportunities through appropriate routing and by achieving efficient spectrum reuse through appropriate link scheduling. We assume centralized scheduling at the base station and focus on minimizing the total schedule length to satisfy a certain traffic demand. Minimizing the schedule length is equivalent to maximizing the system throughput. We present a linear programming optimization model for the joint problem, which relies on the enumeration of all possible schedules. Given its complexity, we decompose the problem using a column generation approach. Our numerical results show that significant gains may be achieved when network coding is incorporated into the design. We compare the performance with that of a joint coding‐oblivious model with and without transmission power control. Copyright © 2011 John Wiley & Sons, Ltd.

We propose a new dynamic row/column management algorithm for freight train scheduling in a single track railway system. While many papers have already been devoted to train scheduling, previously published optimization models still suffer from scalability issues, even for single track railway systems. Moreover, very few of them take into account the capacity constraints, i.e., the number of alternate tracks in the railway stations/sidings in order for the trains to meet/bypass. We propose an optimization model which takes such constraints into account, while still handling efficiently the other meaningful constraints. We design an original solution scheme with iterative additions/removals of constraints/variables in order to remain with a manageable sized mixed integer linear program at each iteration, without threatening to reach the optimal solution. Numerical results are presented on several data instances of CPR (Canadian Pacific Railway) on the Vancouver-Calgary corridor, one of the most busy corridor in their railway system. Therein, the proposed model and algorithm are used as a planning tool to evaluate the network capacity, i.e., how much the number of trains can be increased without impacting significantly the average travel times between the source and destination stations of the various trains in the corridor. Larger data instances than those previously published are solved accurately (epsilon-optimal solutions) for the schedule of freight trains.

We propose a novel network design optimization scheme for greenfield wavelength division multiplexed (WDM) passive optical networks (PONs). For a given OLT and of a set of ONUs, their geographical locations and their corresponding aggregated traffic demand, our proposed BSP (Best Set of PONs) optimization scheme determines the design (location of passive equipment) and dimensioning of the most economical set of PON networks while satisfying unicast/multicast traffic demands and taking into account the signal attenuation constraints.

Providing protection in multi-domain optical networks amounts to ensuring protection for the inter-domain connections. Due to scalability issues, almost all previous studies focused on heuristics. In this study, we propose a large scale optimization ILP model, which allows the exact solution of quite large instances, under the assumption of a distributed network management. The model relies on p-cycles in order to protect the inter-domain links, while FIPP p-cycles are used for the protection in each individual domain, and for the virtual links in between the inter-domain links. Experiments were successfully conducted on a multi-domain network with 5 domains. They include a comparison of bandwidth requirements between the proposed distributed scheme and a centralized scheme.

We propose a novel cross layer optimization scheme for the design and dimensioning of greenfield WDM PON networks. For a given geographical location of the OLT, the ONUs and their corresponding aggregated traffic demand, we propose a generic integer linear programming (ILP) model which optimally and simultaneously: (i) congregates the ONUs into clusters, (ii) determines the type (splitter/ AWG) and number of output ports of the passive switching equipment for all clusters so that all ONUs can be served, (iii) identifies the location of the switching equipment, (iv) determines the proper link dimensioning so as to allow the provisioning of the overall aggregated traffic demand destined to/from the ONUs. The ILP model not only includes the physical layer constraints of PON (i.e., power attenuation and splitting ratio), but the optical layer constraints as well (i.e., number wavelengths carried by the optical fibers depending on the traffic and on the selected switching equipment). The resulting model is therefore the most general model proposed so far, and it guarantees the optimal solution in terms of minimum deployment cost for greenfield WDM PON, with a two stage architecture. Computational results demonstrate the validation and effectiveness of the proposed solution scheme on various data sets with up to 128 ONUs.

In this paper we address the problem of dimensioning infrastructure, comprising both network and server resources, for large-scale decentralized distributed systems such as grids or clouds. We will provide an overview of our work in this area, and in particular focus on how to design the resulting grid/cloud to be resilient against network link and/or server site failures. To this end, we will exploit relocation: under failure conditions, a request may be sent to an alternate destination than the one under failure-free conditions. We will provide a comprehensive overview of related work in this area, and focus in some detail on our own most recent work. The latter comprises a case study where traffic has a known origin, but we assume a degree of freedom as to where its end up being processed, which is typically the case for e.g., grid applications of the bag-of-tasks (BoT) type or for providing cloud services. In particular, we will provide in this paper a new integer linear programming (ILP) formulation to solve the resilient grid/cloud dimensioning problem using failure-dependent backup routes. Our algorithm will simultaneously decide on server and network capacity. We find that in the anycast routing problem we address, the benefit of using failure-dependent (FD) rerouting is limited compared to failure-independent (FID) backup routing. We confirm our earlier findings in terms of network capacity savings achieved by relocation compared to not exploiting relocation (order of 6-10% in the current case studies).

Multi-layer optical networks have recently evolved towards IP-over-WDM networks. Therein, in order to avoid protection/restoration redundancies against either single or multiple failures, synergies need to be developed between IP and optical layers in order to reduce the costs and the energy consumption of the future IP-over-WDM networks. We propose two new optimization models. The first one is an enhanced cutset model, relying on a column generation reformulation. The second one is a path model, based on a multi-flow formulation. Both models can solve exactly most benchmark instances, which were only solved heuristically so far.

This paper investigates design methods of protection schemes in survivable WDM networks that use preconfigured protection structures ($p$-structures) in order to provide different quality-of-recovery (QoR) classes within 100% resilient single-link protection schemes. QoR differentiation is a practical and effective approach in order to strike different balances among protection cost, recovery delay, and management complexity. Based on the degree of pre-cross connectivity of the protection structures, we develop three design approaches of shared protection capacity schemes based on the following: 1) fully pre-cross-connected$p$-structures ($fp$-structures); 2) partially pre-cross-connected$p$-structures ($pp$-structures); and 3) dynamically reconfigured$p$-structures ($dp$-structures). In order to identify the optimal combinations of protection structures to meet the requirements of the three QoR classes, we use a column generation (CG) model that we solve using large-scale optimization techniques. Our CG decomposition approach is based on the separation processes of the design and selection of the protection structures. In the design process of the protection structures, the shape and protection capability of each$p$-structure is decided dynamically during the selection process depending on the network topology and the targeted QoR parameters. Extensive experiments are carried out on several data instances with different design constraints in order to measure the protection capacity cost and the recovery delay for the three QoR classes.

Recently, some push-pull scheduling strategies have been proposed to replace the pull mechanism in mesh based P2P streaming systems. A push-pull mechanism is more efficient in terms of the overheads and leads to a much better playback delay performance since the pull part is mainly used either at startup or to recover lost content. In this work we combine the low scheduling delays of push scheduling with the resiliency and multi-parent ability of mesh overlays. We propose a pure push scheduling strategy, PurePush, where we replace the pull mechanism by a probabilistic push: Parents of a node push a packet with a relaying probability in order to reduce redundancy. Through simulations, we show that PurePush outperforms, with respect to playback delays, a typical push-pull strategy in the realistic situation where we consider packet loss.

Grids can efficiently deal with challenging computational and data processing tasks which cutting edge science is generating today. So-called e-Science grids cope with these complex task by deploying geographically distributed server infrastructure, interconnected by high speed networks. The latter benefit from optical technology, offering low latencies and high bandwidths, thus giving rise to so-called optical grids or lambda grids. In this paper, we address the dimensioning problem of such grids: how to decide how much server infrastructure to deploy, at which locations in a given topology, the amount of network capacity to provide and which routes to follow along them. Compared to earlier work, we propose an integrated solution solving these questions in an integrated way, i.e., we jointly optimize network and server capacity, and incorporate resiliency against both network and server failures. Assuming we are given the amount of resource reservation requests arriving at each network node (where a resource reservation implies to reserve both processing capacity at a server site, and a network connection towards it), we solve the problem of first choosing a predetermined number of server locations to use, and subsequently determine the routes to follow while minimizing resource requirements. In a case study on a meshed European network comprising 28 nodes and 41 links, we show that compared to classical (i.e. without relocation) shared path protection against link failures only, we can offer resilience against both single link and network failures by adding about 55% extra server capacity, and 26% extra wavelengths.

While there are many studies on the efficient design of p-cycles which advertise their spare capacity efficiency, few of them consider such a design under the wavelength continuity assumption, i.e., no wavelength converter at any node. In this paper, we propose to investigate thoroughly the issue of wavelength conversion vs. wavelength continuity for p-cycles, with large scale optimization tools in order to get an exact estimate of the consequences of the wavelength continuity assumption on the spare capacity requirements and on the provisioning cost. Differences with previous work are that we consider exact efficient scalable models instead of heuristics, as well as joint optimization of routing and protection schemes. In addition, with respect to the on-line generation of p-cycles, we allow the simultaneous generation of several node disjoint cycles without hindering a proper consideration of straddling links, leading to a significantly improved scalability. Numerical results show that, although the capacity requirement under the wavelength capacity is higher than under a wavelength continuity assumption, the difference is not significant. Therefore, due to the reduced provisioning cost (saving at least on the converters), designing p-cycles under a wavelength continuity assumption is clearly advantageous.

We propose a p-cycle expanded protection scheme that can guarantee 100% node protection, in addition to 100% protection against single link failures. While some previous studies had already noted that p-cycles can naturally offer some node protection, we show that, at the expense of some p-cycle overlapping, with very mild impact on the bandwidth efficiency, one can guarantee node protection. We propose a design and solution method based on large scale optimization tools, namely Column Generation (CG), that compute p-cycles offering both link and node protection. Previous models offer a solution where a large number of potential cycles needs first to be enumerated, leading to very large ILP models which cannot scale. Comparisons are made between our proposed design approach with the work of Grover and Onguetou (2009). Results show clearly that our approach outperforms their design in terms of capacity efficiency and of the number of distinct cycles. We also evaluate the extra spare capacity requirement of p-cycles for full node protection compared to the one for link protection only. Results shows that p-cycles offering node and link protection only require a slightly larger capacity while the implicit protection against dual link failure is only marginally affected.

With the growing popularity of bandwidth demanding services such as HDTV, VoD, and video conferencing applications, there is an increasing demand on broadband access. To meet this demand, the access networks are evolving from the traditional DSL and cable techniques to a new generation of fiber-based access techniques. While EPONs and GPONs have been the most studied passive optical access networks (PONs), WDM-PON is more often seen as the next generation trend with an hybrid set of switching equipment. We propose a new optimization scheme for the deployment of greenfield WDM PON networks to minimize their total deployment costs. Based on the geographic location of ONUs and their corresponding traffic demand, our proposed scheme optimizes the placement of splitters and AWGs in a WDM PON. The solution process has two phases. In the first phase, ONUs are grouped around switching equipment into different clusters and then each cluster is assigned a passive equipment(i.e.,splitter/AWG). In the second phase, we develop a column generation (CG) algorithm based on a mathematical model, for selecting the best multi-stage placement equipment topology. The resulting combination of the clustering and of the column generation algorithms encompasses the particular cases where all switching equipment are splitters/AWGs/mixture and outputs the location of the switching equipment of the PON network. Numerical results allow the validation of the models and of the algorithms on various data sets.

In a world where an increasing number of transactions are made on the web, there is a need for a trust evaluation tool dealing with uncertainty, e.g., for customers interested in evaluating the trustworthiness of an unknown service provider throughout queries to other customers of unknown reliability. In this paper, we propose to estimate the trust of an unknown agent, say aD, through the information given by a group of agents who have interacted with agent aD. This group of agents is assumed to have an unknown reliability. In order to tackle the uncertainty associated with the trust of unknown agents, we suggest to use possibility distributions. We introduce a new certainty metric to measure the degree of agreement of the information reported by the group of agents about agent aD. Fusion rules are then used to estimate the possibility distribution of agent aD's trust. To the best of our knowledge, this is the first paper that estimates trust, out of empirical data, subject to some uncertainty, in a discrete multi-valued trust environment. Numerical experiments are presented to validate the proposed tools.

Segment p-cycles offer an interesting compromise between the classical (link) p-cycles and the path p-cycles (also known as FIPP p-cycles), inheriting most advantages of both p-cycle schemes. In their original form, segment p-cycles do not offer 100% node protection, i.e., do not guarantee any protection against node failure for the endpoints of the segments. Indeed, if we allow some p-cycle overlapping, it is possible to ensure 100% node protection: this is the focus of the present study. We propose a new efficient design approach for segment p-cycles, called segment Np-cycles, which ensure 100% protection against any single failure, either link or node (endpoints of requests are excluded). In order to evaluate the performances of segment Np-cycles, we develop a new optimization model based on column generation (CG) techniques. The use of such techniques eliminates the need to explicitly enumerate all segment Np-cycle configurations, but instead leads to a process where only improving segment Np-cycle configurations are generated. Numerical results demonstrate that segment Np-cycles are comparable, sometimes even more efficient, than path p-cycles with respect to their capacity requirement. In addition, in order to ensure 100% node protection, they only require a marginal extra spare capacity than the regular segment p-cycles.

Traffic grooming consists of packing low rate streams onto a high speed lightpath in order to effectively use the network resources. Under dynamic traffic, rerouting of ongoing connections has been envisioned as a means, to be used very wisely, to reduce the connection blocking rate and to optimize the network resources. In a context of traffic with QoS constraints, only the delay tolerant ongoing connections are rerouted. In this paper, we design three new heuristics, one relying on a mathematical ILP (Integer Linear Program) model and two low complexity ones to carefully reroute ongoing connection requests in order to accommodate the new incoming connection requests, while minimizing connection disturbance. While the ILP model allows the full exploration of a limit on the overall number of reroutings, both heuristics are designed as low complexity heuristics in order to limit the number of rerouting per establishment of a new incoming connection request. Comparative computational results show that the two low complexity heuristics provide much better results in terms of the best compromise between maximizing the throughput and minimizing the number of disturbances of the already established connection requests.

Nowadays, the Quality of Service (QoS) in Optical Grids has become a key issue. An important QoS factor is resiliency, namely the ability to survive from certain network failures. Although several traditional network protection schemes were devised in the past, they are not optimized for Optical Grids. In an earlier work, we proposed relocation strategies providing backup paths to alternate destinations, exploiting the anycast routing principle of grids. To show the advantage of relocation (compared to traditional network protection) in terms of reduced network capacity, we formulated the network dimensioning problem as an Integer Linear Program (ILP). Yet, its solution exhibited very poor scalability and appeared not practical for reasonably large scale case studies. Therefore, we propose a novel formulation for the relocation protection scheme, using column generation (CG). This approach decomposes the original ILP into two parts, specifically a Restricted Master Problem (RMP) and a Pricing Problem (PP) which are iteratively and alternatively solved until the optimality condition is satisfied. Such a CG decomposition has a significant impact on the complexity of the model, leading to a significant improvement over previous ILPs in term of scalability and running times. We demonstrate that the CG method is highly scalable and generates nearly optimal solutions using case studies with up to 300 connections, showing it to be highly competitive with a previously proposed heuristic. We also perform some comparisons of the anycast scheme with the classical shared path protection on larger network instances.

p-Cycles offer a protection that corresponds to an efficient pre-configured and pre-cross-connected protection scheme. Thereafter, we study the stability and the efficient reconfiguration of p-cycles in the context of dynamic asymmetric traffic. The literature acknowledges it as a difficult problem, but which is of paramount importance in the selection of p-cycles as a protection scheme in Intelligent Optical Networks (IONs). We investigate two p-cycle updating models which differ mainly by their objective criteria. The first objective is the classical one, aiming at minimizing the spare capacity. The second one is new and corresponds to the number of pre-cross-connections that needs to be set/reset after each traffic variation, while attempting to maximize the re-use of previously established pre-cross-connection settings in spite of the modifications of the p-cycles. Note that the second model needs to explicitly include wavelength continuity constraints and is therefore slightly more complex. Results show that: (i) The proposed ILP tools are scalable, and (ii) While p-cycles appear not to be very stable with the first criterion, they emerge as highly stable with the second criterion.

This work introduces a new shared segment protection scheme that ensures both node and link protection in an efficient manner in terms of cost and bandwidth, while taking full advantage of the optical hop endpoints of the primary logical hops (induced by the routing) without adding extra ones for protection. As opposed to the link or path protection schemes, the segment protection scheme has been less studied although it offers an interesting compromise between those two protection schemes, attempting to encompass all their advantages. We investigate two different Shared Segment Protection (SSP) schemes: Basic Shared Segment Protection (BSSP) and Shared Segment Protection with segment Overlap (SSPO), and propose design of 100% single segment protections. In SSPO, we study the extra protection capabilities, node failure and dual link failure survivability, offered by the single 100% segment protection. For both BSSP and SSPO schemes, we propose two novel efficient ILP formulations, based on a column generation mathematical modeling. While (SSPO) offers the advantage over (BSSP) to ensure both node and link protection, it is not necessarily much more costly. Indeed, depending on the network topology and the traffic instances, it can be shown that none of the two SSP schemes dominates the other one. Therefore, the SSPO protection scheme should be favored as it offers more protection, i.e., it adds the node protection to the link protection at the expense of a minor additional cost.

Optical transmission allows massive data transfers thanks to its tremendous transport capacity. Sustained efforts have been made to address the physical constraints that limit its flexibility, but as for today, translucent architectures involving electrical treatments are still favored. Optical Burst Switching (OBS) appears as a promising alternative to Optical Circuit Switching (OCS) in an all-optical framework - provided contention resolution is efficiently solved. In this paper, we investigate further contention resolution with a recourse to the electrical domain. We will thwart the drawbacks of the resulting translucent architecture, i.e., increased delays and equipment cost, by exploiting traffic grooming. Firstly, the contending payload will be submitted to a local aggregation process instead of being stored in dedicated buffers. Secondly, we propose a new transmission scheme, called CAROBS, that exploits dynamic traffic grooming, both at the network edge and in the core network. At the network edge, aggregation queues with different destinations can contribute to build burst trains whose cars can be later optically discarded, one or several at a time, at some intermediate nodes. In the core network, local traffic can be inserted at the tail/head of the train subject to some conditions. A proper dynamic management of the burst trains and of the aggregation pools allows a reduction of the aggregation delays and of the contention rate. Combining our grooming scheme with our translucent architecture annihilates the drawback of signal conversion: Loss-less transfer is achieved without neither impacting the delay nor the equipment cost. It results in an impressive throughput increase that puts OBS close to the performance of OCS with similar features and services, allowing to take full advantage of the high responsiveness to bursty traffic that OBS enjoys.

The focus of this paper is on the minimum cost resource provisioning and nodal equipment location PROVLOC problem for Wide Area Networks (OWANs), i.e., optical networks that cover broad areas. Minimizing the cost means minimizing the network capital and operational expenditures throughout the dimensioning of the nodal equipment, and the location of all-optical cross-connects, while granting all traffic requests. This is done thanks to large scale modeling and optimization tools relying on a scalable column generation method and an efficient rounding off heuristic. Experiments on various network and traffic instances show that a careful dimensioning and location of the nodal equipment can save up to 60% of the number of photonic cross-connects (PXCs), and even more sometimes.

We propose two scheduling and resource allocation schemes that deal with Quality of Service (QoS) requirements in Uplink Long Term Evolution (LTE) systems. QoS for a multiclass system has been seldom taken into account in previous resource allocation algorithms for LTE uplink. In one of the new algorithms, we investigate the possibility of assigning more than one resource block and its consequences on satisfying stringent QoS requirements in the context of heavy traffic, either in terms of end-to-end delays or of minimum rates. System capacity and the number of effectively served requests are used as performance metrics. Numerical results show that it is possible to manage a multiclass scheme while satisfying the QoS constraints of all requests. Allowing the assignment of more than one resource block per request did not appear to be a meaningful advantage. Indeed, it is only useful when there is a heavy traffic, and some of the requests have stringent QoS requirements. But then, satisfying those requests can only be done at the expense of reducing the overall system capacity and of limiting the number of users who can be served.

The problem of scheduling and routing tree construction in WiMAX/802.16 based mesh networks is not defined in the standard and has thus been the subject to extensive research. We consider the problem of joint routing and scheduling in WiMAX-based mesh networks, with the objective of determining a minimum schedule period that satisfies a given (uplink/downlink) traffic demand. Minimizing the length of a schedule amounts to maximizing the spectrum spatial reuse by activating concurrently as many links. This group of transmission links active concurrently is referred to as the transmission group and refers to the set of wireless links that can simultaneously transmit without violating the signal-to-interference-plus-noise ratio (SINR) requirement. Our model is referred to as maximum spatial reuse (MSR). We assume centralized scheduling at the base station and attempt to maximize the system throughput through appropriate routing tree selection and achieving efficient spectrum reuse through opportunistic link scheduling. We present an ILP optimization model for the joint problem, which relies on the enumeration of all possible link schedules. Given its complexity, we decompose the problem using a column generation (CG) approach. We present two formulations for modeling MSR, namely the link-based (CGLink) and the path-based (CGPath) formulation. These two formulations differ mainly in the number of routing decision variables. Our experimental results indicate that the path-based formulation needs much less computational (CPU) time than the link-based in order to determine the (same) optimal solution with the same spatial reuse gain.

All-optical circuit switching prevents contention by forbidding multiplexing beyond the wavelength granularity. The drawbacks of such a coarse granularity can be reduced thanks to translucent architectures with MSPPs (MultiService Provisioning Platforms). Another switching paradigm of interest is of

Loss-less transfers are commonly associated with circuit switching: Circuit switching in all-optical networks (OCS) prevent from collisions by avoiding multiplexing below the wavelength granularity. Spectral multiplexing can be combined with time multiplexing in opaque networks at the expense of add

Several recent P2P streaming systems have adopted mesh overlays to disseminate content to participating peers because this topology appears to be more resilient to churns. To cope with inferred problems, such as data redundancy, these systems opt for data-driven content retrieval mechanisms (pull mechanisms). Each node has a list of neighbors with whom it periodically exchanges buffer information and requests content fragments. One of the drawbacks of such a mechanism is that it does not offer intelligent selection of sending neighbors based on their characteristics. This is mainly because the most important criteria used to select nodes is the content availability. This can result in some performance degradation, for instance, due to peers that are sending very small or big parts of the needed data. Resiliency may then be weakened and overhead increased. In this paper we propose to study how the integration of some end nodes characteristics can improve the performance of a typical pull mechanism with random scheduling. We show that the improvement in performance is significant enough despite the fact that the room for improvement is bounded by the limitations of the pull mechanism. Hence we believe that the awareness of end characteristics is an important block upon which we can build more efficient content retrieval mechanisms. The gain in performance can also be amplified by proposing an alternative to the pull mechanism such as a combined pull-push approach.

In this paper, we present our research aiming at building a petabit router model for next generation networks. Considering the increasing traffic requirements on the Internet, current gigabit and terabit speed routers will soon not be able to meet user demand. One of the promising trends of router evolution is to build next generation routers with enhanced memory capacity and computing resources, distributed across a very high speed switching fabric. The main limitation of the current routing and signaling software modules, traditionally designed in a centralized manner, is that they do not scale in order to fully exploit such an advanced distributed hardware architecture. This paper discusses an implementation for an control plane for next generation routers integrating several protocol dedicated distributed architectures, aiming at increasing the scalability and resiliency. The proposed architecture distributes the processing functions on router cards, i.e., on both control and line cards. Therefore, it reduces the bottlenecks and improves both the overall performance and the resiliency in the presence of faults. Scalability is estimated with respect to the CPU utilization and memory requirements.

The emerging next generation optical transport WDM networks, with reconfigurable optical switches, offer a promising solution to the ever-increasing demand for high bandwidth and flexible connectivity. In order to meet the needs of such a demand, the trend in current backbone and access network development is moving toward a unified solution that will support different classes of service such as voice, data, and a large range of multimedia applications. However, those applications come with different qualities of service (i.e., bandwidth, reliability, and availability) depending on their requirements and on how much the users are willing to pay for the services. In the design of protection schemes in survivable WDM networks, there is a trade-off to be set between the capacity efficiency and the quality of service parameters. Differentiation of the provided quality of service can help in finding an appropriate trade-off between network cost and quality of service, for both service providers and customers. In this paper, we propose different network design optimization models in order to optimize two quality of service (QoS) protection parameters: Protection capacity sharing and recovery delay. We use shared protection schemes based on pre-configured structures that are pre-cross connected ahead of failures, and that are dynamically reconfigured in case of a failure. The resulting optimization models are solved using large scale optimization tools in order to ensure scalable solutions. Comparisons are conducted on different network and traffic instances, and a thorough analysis is made, exploring the added values of pre-cross connected protections structures on protection QoS.

We propose a new design scheme of resilient wavelength division multiplexing (WDM) networks by extending and reshaping pre-configured protection tree (p-tree) structures. The resulting protection scheme relies on optimized pre-cross connected structures that span all previously proposed protection patterns. p-tree-based protection schemes offer the advantages of scalability, local restoration capabilities, and failure impact restriction, but at the same time suffer from capacity inefficiency. While keeping these advantages, we propose an extension (reshaping) of the p-tree protection pattern that imposes no restriction on the shapes of the protection building blocks. Not only the resulting protection scheme remains scalable and highly flexible, but it also leads to pre-configured protection structures that improve much further on capacity efficiency and recovery delay. We establish some new integer linear programming models, and use a large scale optimization tool, named column generation (CG) to solve them. Our CG-based solution method is highly scalable as it does not require an a priori explicit enumeration of the protection structures, but an efficient dynamic enumeration of only the most promising ones. Comparison are made with three other protection schemes, i.e, simple and non-simple p-cycles (fully pre-cross connected structures) as well as p-trees. Results show a clear advantage of the proposed extended-tree scheme with respect to flexibility, capacity efficiency, and restoration delay.

Recently, some push-pull scheduling strategies have been proposed to replace the classical pull mechanism in mesh based P2P streaming systems. A push-pull mechanism is more efficient in terms of the overheads and leads to much better playback delay performance since the pull part is mainly used either at the beginning of the session or to recover lost content. Since a push-pull mechanism typically leads to low scheduling delays, the content delivery delay is impacted mostly by the overlay path length. New peering strategies are then needed to exploit such an advantage. In this paper, we propose two new peering strategies that we compare to a recent proposal of Ren et al. (2008). With resiliency in mind, the strategy variations being compared in this paper impose a fixed number of parents to each node. The two strategies that we propose lead to the lowest playback delays: They lead to overlays with short paths to the source.

The problem of scheduling and tree routing in WiMAX/802.16 based mesh networks were not defined in the standard and are thus subject to extensive research. In this paper, we consider the problem of joint routing and scheduling in 802.16-based wireless mesh network, with the objective of determining a minimum length schedule that satisfies a given (uplink/downlink) end-to-end traffic demand. Minimizing the schedule length amounts to maximizing the spectrum spatial reuse by concurrently transmitting on as many links as possible, which we refer to as a transmission configuration (a group of links that can simultaneously transmit without violating the signal-to-interference-plus- noise ratio (SINR) requirement). Our model is referred to as maximum spatial reuse (MSR). Since there is an overwhelming number of possible transmission configurations to be assigned to time slots, we adopt the column generation technique to construct our MSR model. We present two formulations for modeling MSR, namely the link-based column generation (CGLink) formulation and the path-based column generation (CGPath) formulation. These two formulations differ mainly in the number of routing decision variables. Our experimental results indicate that the path-based formulation needs much less computational (CPU) time than the link-based formulation in order to determine the (same) optimized solution with the same spatial reuse gain.

Peer-to-peer (P2P) systems are quite attractive due to their ability to deliver large amounts of data at a reduced deployment cost. They offer an interesting paradigm for media streaming applications that can benefit from the inherent self organization and resource scalability made available by participating peers. However, most studies on P2P live video streaming deal mainly with the feasibility of such an approach with a focus on maximizing throughput and resiliency. Little has been done to investigate the impact ofthe characteristics of the streaming source and of the participating peers on the P2P system performance and more specifically, on the playback delays experienced by peers. Through the use of an integer linear programming model, this paper investigates several related trade offs we need toconsider, to fully exploit the potential of a P2P streaming system.

WiMax/802.16 mesh network is an emerging infrastructure that offers a cost-effective deployment for highspeed wireless broadband access to the back haul network. However, as in most wireless multi-hop networks, WiMax/802.16 mesh suffers from interference that decreases considerably the throughput and spatial reuse of the network. Interference in WiMax/802.16 mesh is a result of several phenomena, namely concurrent transmissions in the neighborhood and data collisions (that need to be avoided) at a receiver from transmitting nodes that are outside the range of each other (hidden terminal nodes). In this paper, we study the problem of minimizing iInterference (MI) in WiMax/802.16 mesh centralized scheduling networks by appropriately routing end connections and assigning slots to them. The proposed model includes the effect of hidden terminal nodes as well as the interferences coming from neighboring nodes. Results show that power-aware routing and adequate frame size selection yield better network performance, a consequence of the improved network spatial reuse.

We propose a new design approach of survivable WDM networks using simple and non-simple p-cycles-based protected working capacity envelope (PWCE). We investigate the added-value of the non-simple p-cycles over simple p-cycle protection method in terms of capacity efficiency and reliability. As opposed to the prevalent two-step design approach where an explicit enumeration of all/set of p-cycles step is performed ahead of an optimization step, we develop a new optimization approach using a large scale optimization tool named column generation technique, where only few globally optimal cycles are generated dynamically during the optimization process. We conduct performance evaluation experiments on various network topologies, using different metrics in order to measure the added- value of the non-simple p-cycles over simple p-cycles in the design of survivable WDM networks based on PWCE. It is shown that depending on the network topologies, and in particular of their connectivity, significant protection improvement can be achieved when using non simple p-cycles.

WiMax/802.16 mesh network is an emerging infrastructure that offers a cost-effective deployment for high-speed wireless broadband access to the back haul network. In order to provide the best cost-effective deployment solution, nodes must be powered by batteries which do not require electrical cables and voltage transformers deployment (city power lines voltage is not suited to WiMax/802.16 nodes voltage). Moreover this deployment approach (the only one compatible with a mobile nodes topology) is environment constraint free since not all cities have easy-reachable power lines (e.g. rural cities). However it requires a predictive mechanism to calculate the lifetime of the network, in purpose to provide the adequate maintenance (recharge/change nodes batteries, reconfigure the nodes) at the appropriate time. We study the problem of maximizing the network lifetime (MNL) in order to minimize the maintenance of WiMax/802.16 mesh centralized scheduling networks powered by batteries which causes them to go off line. Moreover our study incorporates an explicit novel modeling of interference and hidden terminal nodes using an appropriate time slot allocation. Results show that power aware routing and a convenient frame size improve the network lifetime.

While the advantages of p-cycles and FIPP p-cycles are well established, there has been no systematic analysis of how much bandwidth they consume in comparison with the shared link or path protection schemes. It was also recently observed that, even enumerating a huge number of cycles is not necessarily a guarantee for obtaining good quality solutions with the classical ILP models if tools for large scale programming such as, e.g., column generation techniques, are not used. For instance, a reduction of up to 37% of the solution cost for FIPP p-cycles can be obtained when using column generation instead of classical ILP modeling. We propose to investigate the bandwidth protection costs of p-cycles and FIPP p-cycles in comparison with those of shared link and path protection, using column generation models for the four protection schemes, and therefore obtaining the optimal values for all of them, out of any doubt. Accurate quantitative comparisons show that the average excess required bandwidth is about 6.6% for p-cycles and about 13.4% for FIPP p-cycles in exchange of a much faster restoration time.

The efficient routing of multi-hop connections in WiMax/802.16 based mesh networks poses several challenges, such as dealing with the interferences from concurrent transmissions, addressing the collision problem due to hidden terminals and efficiently utilizing the limited node resources. In this paper, we study the problem of maximizing the network lifetime (MNL) in WiMax/802.16 based mesh networks by appropriately routing end connections and assigning slots to them. The proposed model includes the effect of hidden nodes as well as the interferences coming from neighboring nodes. It shows that power-aware routing yields better network lifetime and better network performance, a consequence of the improved network spatial reuse.

The growing traffic on the core Internet entails new requirements related to scalability and resiliency of the routers. One of the promising trends of router evolution is to build next generation routers with enhanced memory capacity and computing resources, distributed across a very high speed switching fabric. The main limitation of the current routing and signaling software modules, traditionally designed in a centralized manner, is that they do not scale in order to fully exploit such an advanced distributed hardware architecture. This paper discusses an implementation for an OSPF architecture for next generation routers, aiming at increasing the scalability and resiliency. The proposed architecture distributes the OSPF processing functions on router cards, i.e., on both control and line cards. Therefore, it reduces the bottlenecks and improves both the overall performance and the resiliency in the presence of faults. Scalability is estimated with respect to the CPU utilization and memory requirements.

WiMax/802.16 mesh network is an emerging infrastructure that offers a cost-effective deployment for high-capacity wireless broadband access to the backhaul network. Recently, mobility in WiMax/802.16 based mesh networks has been discussed through the IEEE 802.16e standard. Hence, mesh nodes need no longer be stationary, and as a result they will be powered from energy limited batteries. In such networks, radio frequency RF-links become vulnerable to breakage due to nodes mobility and nodes are condemned to failure when their battery is depleted. Adopting this deployment strategy requires a mechanism for selecting the most stable routing paths (with the highest RF-links and nodes availability). In this paper, we develop a mathematical model that considers RF-link and node characteristics in such mesh networks and maximizes the network stability.Namely, our model takes into account the interference caused by adjacent RF-links as well as nodes mobility and energy.Results show that selecting most stable paths augments the longevity of the network's time of operation which in turn leads to a higher data delivery and more satisfied clients.

We investigate the dimensioning of 3G wireless networks with a CDMA2000 radio interface technology. These networks offer a range of multimedia services that require different end-to-end QoS. In order to meet this QoS, dimensioning of a 3G network must include an handshake between the radio and the core networks and therefore involve the three networks (radio, core, access). In this paper we primarily address the problem of optimizing the base station locations and the core network link capacity with different multimedia traffic scenarios and different QoS and GoS requirements. The dimensioning problem is formulated as a mixed integer program (MIP) problem and solved by a tabu search (TS) algorithm that relies on the signal to noise plus interference ratio (SNIR) to guide its search strategy. In order to improve the efficiency of the tabu search, we study extensively various of its key features: (i) search intensification through dynamic tabu lists and aspiration criteria; (ii) search diversification through restarts using new base station locations. We next conduct experiments with the resulting tabu search (TS) on quite large instances. The MIP formulation can be used to evaluate the quality of those solutions. It is then showed that the TS solutions are almost optimal on small instances and requires much less resources than the approximated solutions obtained with the MIP formulations, even for larger instances.

The dynamic routing problem for Overlapping Segment Shared Protection (OSSP) in multi-domain networks has not received a lot of interest so far as it is more complex than in single-domain networks. Difficulties lie in the lack of complete and global knowledge about network topologies and bandwidth allocation whereas this knowledge is easily available in single-domain networks. We propose a two-step routing approach for the OSSP based on a topology aggregation scheme and link cost estimation: an inter-domain step and an intra-domain step. We propose two different heuristics, GROS and DYPOS for the inter-domain step, and a "Blocking-go-back" strategy in order to reduce the blocking rate in the intra-domain step. We compare the performance of the two heuristics against an optimal single-domain approach. We show that both heuristics lead to resource efficient solutions that are not far from the optimal ones. Moreover, both heuristics require relatively small computational efforts and are scalable for multi-domain networks.

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) Global rerouting where the re-optimization is performed once for the entire network; ii) Local rerouting where the re-optimization is serially performed on one domain at a time or on selected domains, and iii) 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. The first model offers the best resource savings while the two others are more scalable in multi-domain networks. Comparative performance of the three models are conducted and numerical results are presented.

Optical burst switching (OBS) is a new optical switching paradigm where traffic can be switched and groomed at a lower level compared to optical circuit switching (OCS). Although research in OBS networks has evolved from theoretical investigations to proof-of-concept demonstrations, several key issues need to be investigated further before OBS prototypes can clearly outperformed OCS networks. While the burst loss rate is often used as the main performance parameter in OBS networks, burst losses come from two sources, contention and insufficient offset time (IOT) due to deflection routing. In this paper, we investigate further the assignment of the offsets and propose an adaptive offset determination that depends on both the bandwidth utilization of the links and nodes traversed by the bursts and some measurement of the burst losses due to insufficient offset time. Numerical results demonstrate that our approach is effective in reducing the network burst drop rate through a reduction of the burst losses due to insufficient offset time. Moreover, it proves to lead to a highly stable IOT burst drop even for dynamic traffic and can be easily controlled, so as to find the equilibrium between the IOT and contention burst drops leading to the minimum burst drop rate

Although many studies have now appeared on solving the routing and wavelength assignment (RWA) problem with full or partial wavelength conversion, it is still unclear to which extend the addition of wavelength converters has a significant or even measurable impact on network bandwidth efficiency or on the blocking rate. Indeed, several authors have observed that the blocking rate is often unchanged even with the addition of converters depending on the traffic instances and the network topology. For this reason, some authors, e.g., Ramaswami and Sasaki (1998) or Erlebach and Stefanakos (2003) have investigated further the usefulness or the impact of adding converters. In this study, we pursue in this direction and investigate two issues: performing some preprocessing tests when solving the RWA problem with/without conversion by identifying, at the outset, some lightpaths that will be present in the optimal solution, and some of the patterns that the traffic instances must contain in order to observe an advantage of adding converters. Conclusions are that quite particular traffic patterns must be present in order for wavelength conversion to be useful, and in that case, it is sufficient to have conversion features at a very limited number of nodes

We consider the problem of traffic grooming in second generation SONET/WDM rings with low-rate traffic circuits associated with a set of heterogeneous rate granularities. While networks are no longer limited by transmission bandwidth, the key issue in WDM network design has evolved towards the processing capabilities of electronic switches, routers and multiplexers. Therefore, we focus here on traffic grooming with minimum interconnecting equipment cost. We first formulate the problem as a generic integer linear programming (ILP) or a mixed integer linear programming (MILP) problem that encompasses several design specifications: UPSR vs. BLSR, non bifurcated vs. bifurcated flows, wavelength continuity constrained or free signal regeneration. Within the context of second generation SONET/WDM rings, we define the cost by a function of the number of transport blades, taking into account that the number of transport blades makes up a significant portion of the overall network cost. Using the CPLEX mixed ILP package, we next compare the optimal solutions of the ILP or MILP programs for different design assumptions, including the classical assumptions with a single hub where the lightpaths directly connect the hub to all other nodes.

We present a review of the various integer linear programming (ILP) formulations that have been proposed for the routing and wavelength assignment problem in WDM optical networks with a unified and simplified notation. We consider both symmetrical and asymmetrical traffic matrices. We propose a new formulation for symmetrical traffic. We show that all formulations proposed under asymmetrical traffic assumptions are equivalent (i.e. same optimal value for their continuous relaxations) although their number of variables and constraints differ. We propose an experimental comparison of various lower and upper bounds with the objective of minimizing the blocking rate, and show that several benchmark problems proposed by Krishnaswamy and Sivarajan (2001) can be solved exactly or with a fairly high precision.

We study mathematical models and discuss optimization algorithms for the dimensioning of 3G multimedia networks. We propose two models which aims at dimensioning networks with both a radio and a core component. The first one is an anticipative one in which we assume that we know a priori the traffic over the planning period and the dimensioning is defined with a best possible call admission control procedure. The second one is a causal one in which we define an explicit call admission control procedure which makes the accept/reject decisions without any knowledge on the forthcoming traffic. We then compare, on an experimental basis, the dimensioning obtained by both models on some multi-service networks.

In this paper, we propose a mathematical model for the dimensioning of a 3G multimedia network and design a Tabu search heuristic to solve it. The model is an anticipative one in which we assume that we know a priori the traffic over the planning period, and the dimensioning is consequently defined with a kind of best possible call admission control procedure. Due to the potentially large number of sessions and periods, solving the mathematical program can be done only for small size instances, so a heuristic approach is required for solving larger instances. Experimental results are provided for some multi-service multi-period problems.

We consider nonlinear programs in 0–1 variables with nonlinear constraints and survey the main approaches to their solution: (i) linearization; (ii) algebraic methods; (iii) enumerative methods and (iv) cutting-plane methods. We also present an extensive computational comparison of algorithms of all four categories. Enumerative methods appear to be the most promising. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

Nilsson recently introduced a rigorous semantic generalization of logic in which the truth values of sentences are probability values. This led to state precisely several basic problems of artificial intelligence, a paradigm of which is probabilistic satisfiability (PSAT): determine, given a set of clauses and probabilities that these clauses are true, whether these probabilities are consistent. We consider several extensions of this model involving intervals on probability values, conditional probabilities and minimal modifications of probability values to ensure satisfiability. Investigating further an approach of G. Georgakopoulos, D. Kavvadias and C. H. Papadimitriou, we propose a column generation algorithm which allows to solve exactly all these extensions. Computational experience shows that large problems, with up to 140 variables and 300 clauses, may be solved in reasonable time. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

The authors study the complexity and propose an algorithm for the problem of determining, given p vectors of {-1,1}(n), all linear combinations of them which are also in {-1,1}(n). Computational results are reported. This problem corresponds to the detection of spurious states in neural networks.