ABSTRACT Studying on networked systems, in which a communication between nodes is functional if their distance under a given metric is lower than a pre‐defined threshold, has received significant attention recently. In this work, we propose a metric to measure network resilience on guaranteeing the pre‐defined performance constraint. This metric is investigated under an optimization problem, namely length‐bounded paths interdiction in continuous domain ( cLPI ), which aims to identify a minimum set of nodes whose changes cause routing paths between nodes become undesirable for the network service. We show the problem is NP‐hard and propose a framework by designing two oracles, threshold blocking ( TB ) and critical path listing ( CPL ), which communicate back and forth to construct a feasible solution to cLPI with theoretical bicriteria approximation guarantees. Based on this framework, we propose two solutions for each oracle. Each combination of one solution to TB and one solution to CPL gives us a solution to cLPI . The bicriteria guarantee of our algorithms allows us to control the solutions' trade‐off between the returned size and the performance accuracy. New insights into the advantages of each solution are further discussed via experimental analysis.

In this work, we study the problem of monotone non-submodular maximization with partition matroid constraint. Although a generalization of this problem has been studied in literature, our work focuses on leveraging properties of partition matroid constraint to (1) propose algorithms with theoretical bound and efficient query complexity; and (2) provide better analysis on theoretical performance guarantee of some existing techniques. We further investigate those algorithms' performance in two applications: Boosting Influence Spread and Video Summarization. Experiments show our algorithms return comparative results to the state-of-the-art algorithms while taking much fewer queries.

Bitcoin is the leading example of a blockchain application that facilitates peer-to-peer transactions without the need for a trusted third party. This paper considers possible attacks related to the decentralized network architecture of Bitcoin. We perform a data driven study of Bitcoin and present possible attacks based on spatial and temporal characteristics of its network. Towards that, we revisit the prior work, dedicated to the study of centralization of Bitcoin nodes over the Internet, through a fine-grained analysis of network distribution, and highlight the increasing centralization of the Bitcoin network over time. As a result, we show that Bitcoin is vulnerable to spatial, temporal, spatio-temporal, and logical partitioning attacks with an increased attack feasibility due to the network dynamics. We verify our observations through data-driven analyses and simulations, and discuss the implications of each attack on the Bitcoin network. We conclude with suggested countermeasures.

Utility providers are gradually deploying social networks as a useful addition to the Smart Grid in order to help engage consumers in energy management and efficient usage. Besides its benefits, is there any negative impact to the Smart Grid? In this paper, we investigate the vulnerability of Smart Grid when integrating into social networks, where attackers utilize misinformation propagation in social network to alter electricity customer's behavior with the goal of causing degradation to power infrastructure. Stand in both perspectives of power facility administrator and adversary, we model the vulnerability assessment of the system under an optimization problem, which enables us to provide theoretical analysis and behavior investigation of the system based on the complexity theory. As solving the problem is challenging, we propose heuristic solutions and show their efficiency on assessing the system's vulnerability in the presence of misinformation attacks. Therefore, we conclude that misinformation attacks must be considered when developing the security model for Socially-enabled Smart Grid technology and planning mitigation techniques.

A major challenge in blockchain sharding protocols is that more than 95% transactions are cross-shard. Not only those cross-shard transactions degrade the system throughput but also double the confirmation time, and exhaust an already scarce network bandwidth. Are cross-shard transactions imminent for sharding schemes? In this paper, we propose a new sharding paradigm, called OptChain, in which cross-shard transactions are minimized, resulting in almost twice faster confirmation time and throughput. By treating transactions as a stream of nodes in an online graph, OptChain utilizes a lightweight and on-the-fly transaction placement method to group both related and soon-related transactions into the same shards. At the same time, OptChain maintains a temporal balance among shards to guarantee the high parallelism. Our comprehensive and large-scale simulation using Oversim P2P library confirms a significant boost in performance with up to 10 folds reduction in cross-shard transactions, more than twice reduction in confirmation time, and 50% increase in throughput. When combined with Omniledger sharding protocol, OptChain delivers a 6000 transactions per second throughput with 10.5s confirmation time.

Motivated by various settings, we study a new Influence Maximization problem at the Community level (IMC) which aims at finding k users to maximize the benefit of influenced communities where a community is influenced iff the number of influenced users belong to this community exceeds its predefined threshold. In general, IMC objective function is not submodular nor supermodular, thereby making it very challenging to apply existing greedy solutions of the classic influence maximization (IM) where submodular function is required. Furthermore, the major challenge in the traditional methods for any related IM problem is the inefficiency in estimating the influence spread. IMC brings this difficulty to a higher level when considering influenced communities instead of influencing each individual user. In this paper, we propose different approximation algorithms for IMC: (1) Using Sandwich approach with a tight submodular function to bound the IMC objective function, (2) Activating the top-k influencing nodes found from network sampling. Furthermore, when the activated thresholds of communities are bounded by a constant, we propose an algorithm with performance guarantee tight to the inapproximability of IMC assuming the exponential time hypothesis. Each algorithm has its own strengths in a trade-off between effectiveness and running time, which are illustrated both in theory and comprehensive experimental evaluation.

Bitcoin is the leading example of a blockchain application that facilitates peer-to-peer transactions without the need for a trusted intermediary. This paper considers possible attacks related to the decentralized network architecture of Bitcoin. We perform a data driven study of Bitcoin and present possible attacks based on spatial and temporal characteristics of its network. Towards that, we revisit the prior work, dedicated to the study of centralization of Bitcoin nodes over the Internet, through a fine-grained analysis of network distribution, and highlight the increasing centralization of the Bitcoin network over time. As a result, we show that Bitcoin is vulnerable to spatial, temporal, spatio-temporal, and logical partitioning attacks with an increased attack feasibility due to network dynamics. We verify our observations by simulating attack scenarios and the implications of each attack on the Bitcoin . We conclude with suggested countermeasures.

As the existing power grid becomes increasingly complex, the deployment of Smart Grids-which can significantly improve the stability and efficiency of power infrastructure-has seen increasing interest. However, with new technology comes new security concerns. Recent work has shown that fabricating valid but malicious messages on a Smart Grid's SCADA network can cause widespread power outages. Moreover, the large scale, complexity, and tight constraints of these networks makes deploying in-line detection systems insufficient. A common approach is to instead conduct whole-network audits by temporarily duplicating & forwarding all network traffic to a server dedicated to detecting malicious content. This is usually done by taking advantage of port- mirroring to duplicate the packets received with minimal overhead. However, the operation of these audits sees a number of challenges. For instance, each router used to collect traffic demands physical set-up - thus there is a real cost to needlessly high coverage. In this work, we consider the problem ofefficientlyfinding the minimal set of routers in the SCADA network to use for auditing traffic. This efficiency is critical for enabling timely auditing. Similar versions of this problem have seen study. However, they suffer either from a severe mismatch w.r.t. the problem domain, or from serious scalability concerns. This motivates us to devise a novel (2+θ)(ln|V|+1) approximation algorithm for this problem with a 2-approximation for the special case of tree networks. We experimentally evaluate our solution and compare it to an optimal IP formulation, finding that it performs near-optimally on small networks and significantly outperforms heuristics in all cases.

A computer-aided approach to the planning of SS/TDMA network operation is proposed. SS/TDMA is a sophisticated satellite communication network based on an onboard switch matrix, whose operation planning is formulated as a large-scale scheduling problem. An overall planning and scheduling model is presented to deal with practical SS/TDMA systems, such as a two-frequency channel network and nondisjoint beam coverage. For systematic planning suitable for a computer-aided approach, the entire scheduling process is divided into several steps, for each of which an efficient mathematical model is proposed. A linear programming model is used for distribution of traffic on a beam-to-beam basis and the generated switching sequence is further refined by a model using the traveling salesman problem. Burst scheduling is carried out by the Bin packing algorithm and scheduling models for practical networks allowing transponder hopping and multidestination bursts. An algorithm called enhanced rescheduling is presented to further improve the scheduling capability of the existing methods. The performance of the proposed methods is demonstrated by simulation results.>

Efficient algorithms that generate a detailed operation plan for satellite-switched time-division multiple access (SS/TDMA) systems are proposed. A burst time plan generation problem is analyzed and two algorithms for burst scheduling are presented. The first method is an algorithm based upon a bin pack problem. The other algorithm schedules new bursts while reassigning already scheduled bursts by a single machine scheduling model. These algorithms are shown to be applicable to practical systems operating with transponder hopping and multidestination bursts. Simulation results for a number of example problems are presented.>

When two or more frequency-modulated and/or digital carriers of various sizes and modulation formats are transmitted through a common memoryless nonlinear device with AM/AM and AM/PM characteristics such as a traveling-wave tube amplifier, interactions among the carriers will occur. One of the impairments caused by these interactions results in modulation-transfer noise effects. In particular, in satellite communications, depending on the manner multicarrier transponders are used, the modulation-transfer impairment manifests itself under various forms and subjective interference effects. This tutorial-review paper presents an introduction to this type of impairment, methods of analysis and examples, and measurement results. General practical guidelines are suggested for controlling these effects.

An analysis of the modulation transfer noise effects from a continuous (nonbursty) digital carrier to multiple FDM/FM carriers in a common memoryless nonlinear amplifier (e.g., satellite transponder TWTA) is presented. It is shown that the modulation transfer noise, which is caused by the random envelope variations of the digital carrier due to the random data patterns and filtering of the PSK pulses, consists of both discrete and continuous spectral components in the baseband of the FDM/FM carriers. Numerical examples in terms of the noise power ratio as well as a comparison between measured and computed results are given. In general, the discrete or tonal interference component at the symbol rate of the digital carrier is quite significant. Results of this paper should be useful in the planning of FDMA satellite transponders employing the mixed PSK-FM mode of operation.

This paper presents a power series expansion approach for evaluating modulation transfer noise effects fromLdigital carriers (continuous or bursty) toKFDM/FM carriers in a common memoryless nonlinear amplifier. The method allows for a complete characterization and assessment of this type of transmission impairment and its effects in satellite communications systems. The baseband modulation transfer noise in the FM carriers caused by the random envelope fluctuations due to filtering of PSK pulses and/or by the on-off bursting of the digital carriers can be calculated. Illustrative numerical results indicate that the mixed PSK-FM mode of operation in satellite transponders should be employed with great care since a number of 4 kHz channels in the basebands of the FM carriers may receive prohibitive interference.

This paper examines modulation transfer noise effects from TDMA carriers to FDM/FM carriers in a common memoryless nonlinear amplifier. The modulation transfer noise consists of discrete as well as continuous spectral components. Three types of discrete components are identified: those due to pulse filtering only, those due to on-off bursting only, and cross terms due to both mechanisms simultaneously. The continuous spectral component of the modulation transfer noise is due to pulse filtering only. A comparison of the relative intensities of all these noise components is also presented.

The Bessel function expansion has been used [1] to approximate the TWTA nonlinear characteristics to assist in the evaluation of intelligible crosstalk between FDM/FM carriers using the Shimbo-Pontano method [2]. In particular, the arbitrary constant α was chosen to be in the range of 100-1000. This correspondence presents a further theoretical clarification on the selection of suitable values for α, which was briefly explained in [3]. In this analysis, it is shown that the suitably chosen values for α (as given in the main text) cannot be large (roughly,\alpha \leq 1.6).

A method of evaluating double intelligible crosstalk between two frequency division multiplexed frequency modulated (FDM/FM) carriers accessing the same earth station high-power amplifier (HPA) and satellite transponder traveling wave tube amplifier (TWTA) has been developed. The analysis takes into consideration the AM/AM and AM/PM characteristics of the two cascaded memoryless nonlinear amplifiers, and the amplitude and group delay variations of transmission paths preceding the first nonlinear amplifier and of the path between the two nonlinear amplifiers. Results of the double intelligible crosstalk evaluation show the existence of significant distortion cross terms caused by the two cascaded nonlinearities and filters, in addition to individual distortion terms by each nonlinearity. Specific illustrative examples are discussed, and some practical suggestions are given for controlling crosstalk impairment effects in satellite channels with double cascaded nonlinear amplifiers.

An investigation of ways to improve the capacity in a dedicated SCPC transponder has resulted in the development of a method for optimizing the transponder capacity and link performance in preassigned multilevel SCPC systems. The main approach is to form different groups of carriers based on the traffic requirement, and on typical characteristics of the link destinations such as variations in the satellite e.i.r.p. and downlink path loss, and differences in the receive earth station antenna size. The Fletcher-Powell optimization technique is used to determine the set of optimum carrier levels at the transponder TWTA input. Application of the method to a number of preassigned multilevel frequency plans in a global transponder environment clearly indicates that the total carrier-to-noise ratios for all the links can be optimized at any specified CNR value, and that the optimized capacities are substantially higher than that of the basic two-level system. The implementation of multilevel plans is fairly simple if all downlink carrier levels can be monitored at some reference station in the SCPC network to reasonably control the uplink e.i.r.p. levels.