Cloud gaming offers excellent potential; however, it presents significant challenges for 5G networks because of its strict requirements for high reliability and low latency. Cloud gaming service deployment can be modeled as a Virtual Network Functions Chain Placement Problem (VNF-CPP), where a service instance is represented by a chain of interconnected Virtual Network Functions (VNFs). Solving the VNF-CPP may result in infeasible solutions when the underlying network infrastructure can not meet the service requirements. In this paper, we propose an automatic feasibility restoration technique and explain how network operators can use it to meet cloud gaming's demands. Our proposed algorithms reveal the origins of the infeasibilities so that network operators can understand the reasons behind them. Moreover, the algorithms suggest the best way to alter the network to regain feasibility by providing realtime elastic resource management. Specifically, two approaches are proposed and evaluated. The first approach is the Irreducible Infeasible Set (IIS) Repair, and the second is the Minimum Cost Redesign. We evaluate the proposed algorithms using two practical use cases: an offline use case, where we need to fix the infeasibility for a bulk of service instances, and an online use case, where we need to fix the infeasibility for a single service instance in realtime. Furthermore, theoretical analysis and results show that the Minimum Cost Redesign method outperforms the IIS Repair method. Results also verify that our algorithms can provide practical solutions for both use cases in realtime.

A distributed wireless backhaul has emerged as an attractive solution for forwarding traffic to the core in 5G Ultra-Dense Networks (UDNs). It consists of a large number of small cells and a few of these cells, referred to as gateways, are linked to the core by high capacity fiber optic links. Each small cell is associated to one gateway and forwards its traffic to it directly or through multiple hops. The backhaul network capacity increases by decreasing the average number of hops. In this paper, we consider two machine learning-based clustering algorithms, namely, k-means and k-medoids, to find gateway locations that minimize the average number of hops. We compare their performance with a baseline approach at different small cell densities through extensive Monte Carlo simulations in terms of average number of hops. The results indicate that both clustering algorithms significantly outperform the baseline approach and k-medoids performs equal to or better than k-means.

Management of large service centers and clouds requires adaptation to changing conditions and workload. Optimal deployments are possible on private clouds if there is full knowledge of the applications. Previous work,CloudOpt,combines large-scale linear optimization with a detailed non-linear performance model of every application to determine such deployments. However, when conditions change the new solution is independent of the previous deployment, and often requires excessive changes. Practical adaptive management needs a controlled compromise between the effort and cost of changing the current deployment, and the value lost by not making a change. This paper enhances CloudOpt by incorporating adjustablepersistencetechniques to constrain the deployment changes in each update. Three such techniques are compared, and the best ones reduce the reconfiguration effort at each adaptation step by about 90 percent, with about a 5-10 percent penalty in running costs. Persistence techniques impose no reduction in the scalability of CloudOpt.

As the sizes of CMOS devices rapidly scale deep into the nanometer range, the manufacture of nanocircuits will become extremely complex and will inevitably introduce more defects, including more transient faults that appear during operation. For this reason, accurately calculating the reliability of future designs will be extremely critical for nanocircuit designers as they investigate design alternatives to optimize the tradeoffs between area-power-delay and reliability. However, accurate calculation of the reliability of large and highly connected circuits is complex and very time consuming. This paper presents a complete solution for estimating logic circuit reliability bounds with high accuracy in reasonable time, even for very large and complex circuits. The solution combines a novel criticality scoring algorithm to rank the reliability of individual input vectors with a heuristic search to find the input vector having the lowest reliability. The solution scales well with circuit size, and is independent of the interconnect complexity or the logic depth. Extensive computational results show that the speed of our method is orders of magnitude faster than exact solutions provided by Bayesian network exact inferences, while maintaining identical or sufficiently close accuracy.

In a classical multi-radio multi-channel Wireless Mesh Network (WMN) architecture, mesh nodes use omni-directional antennas. Due to the circular radiation pattern of such antennas, when a mesh node communicates with its neighbor on a certain frequency channel, other mesh nodes within its range must remain silent. Directional antennas have been proposed as a way to improve spatial reuse. Since these antennas are non-steerable, they are not suitable for a dynamic WMN. In this paper, we address the problem of co-channel interference in a dynamic WMN environment by using beamforming based on utilizing the multiple omni-directional antennas of a multi-radio mesh node in the form of a linear antenna array. Our novel Linear Array Beamforming-based Channel Assignment method reduces the number of frequency channels required (NCR) for interference-free communication among the mesh nodes. It significantly outperforms the classical omni-directional antenna pattern-based channel assignment approach in terms of NCR for all node-degrees.

Current cloud management systems have limited awareness of the user application, and application managers have no awareness of the state of the cloud. For applications with strong real-time requirements, distributed across new multi-cloud environments, this lack of awareness hampers response-time assurance, efficient deployment and rapid adaptation to changing workloads. This paper considers what forms this awareness may take, how it can be exploited in managing the applications and the clouds, and how it can influence cloud architecture.

In a multi-radio multi-channel wireless mesh network, a channel assignment that is based on a fixed number of available frequency channels may cause co-channel interference, which degrades the network throughput. We address this problem by ensuring interference-free communication among the mesh nodes. The main purpose of this work is to determine the minimum number of non-overlapping frequency channels required for interference-free channel assignment in order to achieve the maximum network throughput while maintaining fairness among the multiple network flows, given the location of the mesh nodes and the number of their half-duplex radio interfaces. To minimize the number of channels required, we apply our Select x for less than x Topology Control Algorithm to build the connectivity graph instead of using the classical approach based on maximum power (MP). We show that our approach outperforms the MP-based approach in terms of the number of channels required as well as the links to channels ratio for all node-degrees.

On behalf of the Editorial Board, I would like to thank the following people, who acted as Referees during the past year.

When deploying services in a cloud, a balance must be found between performance and capacity of the service, and the memory available on nodes. This is further complicated if the number of replicas of an application is limited, for instance by the available number of licenses. The analysis of interference between services must scale to large numbers of host nodes, applications, replicas of applications, and classes of users. This paper combines a multi-dimensional packing heuristic and network flow optimization to satisfy simultaneous constraints on throughputs, processor utilizations, memory availability and license availability, at a minimum cost and with a minimum of host processors.

On behalf of the Editorial Board, I would like to thank the following people, who acted as Referees during the past year.

My research in optimization at the Department of Systems and Computer Engineering at Carleton University has brought me into contact with researchers in the Department of Electronics, our sister department in the general field of Electrical and Computer Engineering (ECE), which has a major research thrust in computer-aided design (CAD) of very large scale integrated (VLSI) circuits. I have come to realize that the design of VLSI systems consists in large part of solving incredibly massive mixed-integer nonlinear optimization problems, together with enormous circuit simulations. This is impossible without the use of CAD techniques. Over time, ECE-CAD researchers have both borrowed useful standard techniques from operations research (OR) and have invented their own, often to deal with the sheer scale and complexity of the design problems they face. Interaction between the OR and ECE-CAD communities would seem to be a natural development. Coincidentally, the INFORMS Journal on Computing had an area entitled “High Performance Computation” that covered (i) the solution of OR problems using new computing technologies, (ii) the application of OR techniques in the design and use of highperformance computing and communication systems, and (iii) solution methods for ultra-large-scale OR applications. The viability of this area was debated during 2003 as some of its aspects migrated to other areas (e.g., the new “Telecommunications and Electronic Commerce” area), and the number of submissions declined. The area was eventually closed, although I argued that the overlap between OR and ECE-CAD, essentially covering items (ii) and (iii), was a very active research area. This Special Cluster of papers was conceived as a way to test that argument. I was recruited at the same time to prepare a tutorial on ECE-CAD for the 2004 INFORMS Annual Meeting (see John W. Chinneck, Michel Nakhla, and Q. J. Zhang 2004. Computer-aided design for electrical and computer engineering. H. J. Greenberg, ed. Tutorials on Emerging Methodologies and Applications in Operations Research. Springer, New York, 6-1 to 6-44). The preparation of the article reinforced my observation about the research overlap between OR and ECE-CAD. A search of the electrical engineering literature for 2000 through early 2004 turned up 46,725 papers mentioning “simulate” or “simulation” as keywords in the abstract, 14,216 papers mentioning “optimization” or “optimize,” and relatively smaller numbers for specific techniques such as “neural network” (6,251), “genetic algorithm” (2,603), “linear programming” (576), “simulated annealing” (448), and “branch and bound” (199). One surprise was the relatively small number of papers using the generic keywords “mathematical programming” (68) or “operations research” (37). The general conclusion of the tutorial article is that the OR and the ECE-CAD communities have much to offer each other. This is certainly the case for the papers gathered in this Special Cluster. We see known OR techniques adapted for use in ECECAD. In “Integer Linear Programming Models for Global Routing,” Behjat et al. apply integer linear programming in a heuristic to solve enormous NPhard connection routing problems for VLSI circuits. In “Task Scheduling in a Finite-Resource, Reconfigurable Hardware/Software Codesign Environment,” Loo and Wells use simulated annealing, genetic algorithms, and random search techniques to solve scheduling problems in hardware-software co-design. We also see new techniques specifically developed by the ECE-CAD community to deal with problems of extreme scale. In “A Projection-Based Reduction Approach to Computing Sensitivity of Steady-State Response of Nonlinear Circuits,” Pai et al. develop methods for sensitivity analysis in extremely large nonlinear programs, especially those in which the objective function is very costly to evaluate. The methods have special relevance for simulation-based

This paper develops a method for moving quickly and cheaply from an arbitrary initial point at an extreme distance from the feasible region to a point that is relatively near the feasible region of a nonlinearly constrained model. The method is a variant of a projection algorithm that is shown to be robust, even in the presence of nonconvex constraints and infeasibility. Empirical results are presented.

Abstract Wireless networks are evolving to include Internet access to interactive multimedia and video conferencing as well as traditional services such as voice, email and web access. These new applications can demand large amounts of network resources, such as bandwidth, to achieve the highest levels of quality (e.g. picture quality). In conjunction with this trend, charging and resource allocation systems must evolve to explicitly consider the trade‐off between resource consumption and the Quality of Service (QoS) provided. This paper proposes a novel QoS‐based charging and resource allocation framework. The framework allocates resources to customers based on their QoS perceptions and requirements, thereby charging fairly while improving resource allocation efficiency. It also allows the network operators to pursue a wide variety of policy options, including maximizing revenue or using auction or utility‐based pricing. Copyright © 2003 John Wiley & Sons, Ltd.

Given an infeasible set of linear constraints, finding the maximum cardinality feasible subsystem is known as the maximum feasible subsystem problem. This problem is known to be NP-hard, but has many practical applications. This paper presents improved heuristics for solving the maximum feasible subsystem problem that are significantly faster than the original, but still highly accurate.

Algorithms and computer-based tools for analyzing infeasible linear and nonlinear programs have been developed in recent years, but few such tools exist for infeasible mixed-integer or integer linear programs. One approach that has proven especially useful for infeasible linear programs is the isolation of an Irreducible Infeasible Set of constraints (IIS), a subset of the constraints defining the overall linear program that is itself infeasible, but for which any proper subset is feasible. Isolating an IIS from the larger model speeds the diagnosis and repair of the model by focussing the analytic effort. This paper describes and tests algorithms for finding small infeasible sets in infeasible mixed-integer and integer linear programs; where possible these small sets are IISs.

Infeasibility is often encountered during the process of initial model formulation or reformulation, and it can be extremely difficult to diagnose the cause, especially in large linear programs. While explanation of the error is the domain of humans or artificially intelligent assistants, algorithmic assistance is available to isolate the infeasibility to a subset of the constraints, which helps speed the diagnosis. The isolation should be infeasible, of course, and should not contain any constraints which do not contribute to the infeasibility. Algorithms for finding such irreducible inconsistent systems (IISs) of constraints have been proposed, implemented, and tested in recent years. Experience with IISs shows that a further property of the isolation is highly desirable for easing diagnosis: the isolation should contain as few model rows as possible. This article addresses the problem of finding IISs having few rows in infeasible linear programs. Theory is developed, then implemented and tested on a range of problems using a modified version of MINOS 5.4 called MINOS(IIS).

Network models are among the largest linear programs solved, but formulation can be a bottleneck. Errors may be introduced during formulation, reformulation, or when combining several smaller models into one large model (as is often done in econometrics). Simply knowing that the model is infeasible is not enough: where there are many nodes and arcs, the modeler needs guidance as to where repairs are needed (localization), and some indication of the cause of the error (diagnosis). The state of the art flow balancing methods for analyzing infeasible networks simply do not provide enough localization or diagnosis, and in addition cannot operate on advanced netforms. The paper presents an infeasibility analysis procedure for all classes of network models that localizes the error to a minimal causative set of nodes, arcs, and constraints, and provides a basic diagnosis. The procedure builds on previous work[3, 5, 6] but tunes the methods for the special case of networks. Examples are given, using solutions provided by PROFLOW, software for the formulation, analysis and solution of network models.

With ongoing advances in hardware and software, the bottleneck in linear programming is no longer a model solution, it is the correct formulation of large models in the first place. During initial formulation (or modification), a very large model may prove infeasible, but it is often difficult to determine how to correct it. We present a formulation aid which analyzes infeasible LPs and identifies minimal sets of inconsistent constraints from among the perhaps very large set of constraints defining the problem. This information helps to focus the search for a diagnosis of the problem, speeding the repair of the model. We present a series of filtering routines and a final integrated algorithm which guarantees the identification of at least one minimal set of inconsistent constraints. This guarantee is a significant advantage over previous methods. The algorithms are simple, relatively efficient, and easily incorporated into standard LP solvers. Preliminary computational results are reported. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

Review of: Bertsekas, D. P., and Tsitsiklis (1989) Parallel and Distributed Computation: Numerical Methods, Prentice-Hall, Englewood Cliffs, NJ. Reviewed by: Harvey J. Greenberg. Review of: Van Hentenryck, Pascal (1989) Constraint Satisfaction in Logic Programming, MIT Press, Cambridge, MA. Reviewed by: John W. Chinneck and Gerald M. Karam. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

It is the author's premise that it is possible to gain a better understanding of systems theory and the modeling process by examining the anomalous heat flow model. This examination suggests new areas for research in systems theory. The product of the through and across variables does not yield power, an inductive component does not exist, and the through variable is not measured in the usual way. A closer study of these anomalies has broad implications for the methods of systems theory in general. Among these implications are (1) for every physical phenomenon there is a variable set that provides all of the generic characteristics; (2) every physical system has an alternate formulation using energy flow rate as the `through variable'; (3) physical systems that would normally be modeled using discrete variable sets can be united in a single model; and (4) methodological advances are required in order to deal with random diffusion processes such as heat flow. Further, some insight is gained into the effect of a macroscopic versus a microscopic viewpoint in model building.