Hosting virtual network function (VNF) on the edge devices in modern IoT networks significantly reduces the number of appliance hardware needed. It also expedites significant routing and load-balancing processes and reduces power consumption and maintenance costs for an extensive network. Therefore, placing VNFs on edge devices with efficient resource utilization to serve the growing number of IoT devices is an important research question for the network community. This research proposes a many-to-many VNF placement model with fairness built in. One user (IoT device) can access multiple VNFs, and many VNFs can be hosted into a single host (edge device). We give an optimization model and valid inequalities for the optimal placement of VNFs to minimize the total latency. A branch and cut algorithm is also developed here for solving the model optimally. We evaluate the model with synthetic data for a many-to-many and one-to-one mapping of VNFs and hosts. A detailed simulation shows that the proposed algorithm(s) can produce an optimal and fair placement in near real-time on realistically sized instances.

Our aim is to determine conditions for quantum computing technology to give rise to security risks associated with quantum Bitcoin mining. Specifically, we determine the speed and energy efficiency a quantum computer needs to offer an advantage over classical mining. We analyze the setting in which the Bitcoin network is entirely classical except for a single quantum miner who has a small hash rate compared to that of the network. We develop a closed-form approximation for the probability that the quantum miner successfully mines a block, with this probability dependent on the number of Grover iterations the quantum miner applies before making a measurement. Next, we show that for a quantum miner that is “peaceful”, this success probability is maximized if the quantum miner applies Grover iterations for 16 minutes before measuring, which is surprising as the network mines blocks every 10 minutes on average. Using this optimal mining procedure, we show that the quantum miner outperforms a classical computer in efficiency (cost per block) if the condition Q < Crb is satisfied, where Q is the cost of a Grover iteration, C is the cost of a classical hash, r is the quantum miner's speed in Grover iterations per second, and b is a factor that attains its maximum if the quantum miner uses our optimal mining procedure. This condition lays the foundation for determining when quantum mining, and the known security risks associated with it, will arise.

Efficient propagation of data across mobile nodes is essential in wireless networks. A minimum connected dominating set (MCDS) of nodes is typically used to reduce redundant transmission in broadcasts. If a group of nodes wants to transmit over a shared channel simultaneously, then contention occurs. Contending nodes then defer transmissions for a random time. A contention aware connected dominating set (CACDS) that minimizes transmission conflict is therefore essential. We study integer programming formulations computationally for MCDS and CACDS. We use Benders decomposition to solve them and propose a new method to compute Bender’s feasibility cut based on the number of connected components.We evaluate the state-of-art approach computationally for MCDS and CACDS based on the shortest paths with our approach. The detailed experiments show that the new method takes less time and minimizes contention better in large networks.

Device-to-device (D2D) communication in an underlaying cellular network is becoming increasingly common in telecommunication systems, and it will play a vital role in the fifth generation (5G) and beyond. The base stations manage the cellular users. The D2D pairs communicate directly without using the base station. This direct and short-range communication of D2D pairs improve the energy efficiency. It also enables inter-device applications such as location-based emergency services, commercial advertisements, etc. D2D pairs share spectrum resources from cellular users. This sharing generates a significant amount of interference in mobile communication. We study the problem of assigning resources from cellular users to D2D pairs such that the total interference is minimized subject to a minimum target sum rate. We give a two-phase combinatorial algorithm which computes an allocation of resources subject to the sum rate constraint. For the case when the interference between any communicating D2D pair is uniform, the algorithm finds an optimal solution in polynomial time.

Several authors have quantified the modularity of software systems in terms of coupling and cohesion metrics. Most of these approaches focus on functional and procedural dependencies in the system. Although highly relevant at the design phase, these static dependencies alone do not account for how a software product evolves over time. Instead, this is also dictated by logical and hidden dependencies between system files. To a large extent, the co-change (co-commit) relation captures these different types of dependencies. In this paper, we define two measures of co-change-modularity of a software product based on a weighted design structure matrix (DSM). The first metric, called the weighted propagation cost, uses matrix exponential to measure how changes to one system file potentially affect the whole product. The second metric, called the weighted clustering cost, uses the output of the first metric to measure the partitionability of the system based on the co-change relation. In addition, we provide a visual representation of how the co-change structure of a system evolves over time. We discuss the theoretical foundation of our work and highlight its advantages over existing methodologies. We apply our approach to GNU Octave and show the findings to be consistent with the available literature on the evolution of Octave. Our analysis is extensible and applicable to a range of scenarios including open source systems.

We consider the problem of allocating clients to base stations in wireless networks. Two design decisions are the location of the base stations, and the power levels of the base stations. We model the interference, due to the increased power usage resulting in greater serving radius, as capacities that are non-increasing with respect to the covering radius. Clients have demands that are not necessarily uniform and the capacity of a facility limits the total demand that can be served by the facility. We consider three models. In the first model, the location of the base stations and the clients are fixed, and the problem is to determine the serving radius for each base station so as to serve a set of clients with maximum total profit subject to the capacity constraints of the base stations. In the second model, each client has an associated demand in addition to its profit. A fixed number of facilities have to be opened from a candidate set of locations. The goal is to serve clients so as to maximize the profit subject to the capacity constraints. In the third model, the location and the serving radius of the base stations are to be determined. There are costs associated with opening the base stations, and the goal is to open a set of base stations of minimum total cost so as to serve the entire demand subject to the capacity constraints at the base stations. We show that for the first model the problem is NP-complete even when there are only two choices for the serving radius, and the capacities are 1,2. For the second model, we give a 1/2 approximation algorithm. For the third model, we give a column generation procedure for solving the standard linear programming model, and a randomized rounding procedure. We establish the efficacy of the column generation based rounding scheme on randomly generated instances.